DiIzhan's blog

How to write random?
By DiIzhan, history, 9 years ago, In Russian

Hi, Codeforces! I usually create a testset founded on rand (), but the range of this function is 10^5. And if I want to generate a big number, I used to write a function like this

llong randomize (llong x) {
	llong res = 1;
	for (llong i = 1; i <= 5; ++ i) {
		res *= rand () * 1LL;
		res %= x;
	} return res % x + 1;
}

but there's high probability of returning 1.

If you have an effective method of using rand () function, please, write your way.

P.S. sorry for bad english.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I think you can use mt19937_64.

→ Reply
»
9 years ago, hide # |
← Rev. 2  
Vote: I like it +5 Vote: I do not like it

It's not 105. Afaik, it's compiler-defined. If you use MinGW on Windows, chances are its range is [0; 32767].

I use the following hack so it works both on Windows and Linux within [0; 2^30) in practice:

int randint(int l, int r) {
  int v = (rand() << 15) ^ rand();
  v %= r - l + 1;
  return v + l;
}

Good property: if rand() is uniform, this function is almost uniform as well (first values between l and r are slightly more likely).

→ Reply