DiIzhan's blog

How to write random?
By DiIzhan, history, 7 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

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

I think you can use mt19937_64.

→ Reply
»
7 years ago, # |
← 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
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    But it may return negative numbers even if l and r are positive.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You mean the situation when v overflows and becomes a negative?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        I wrote long long instead of int + l and r were small enough

        → Reply