Psuedo-random number generators and modulo

This topic is 5064 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I've heard it mentioned on occasion that using the modulo operator on a random number (e.g. rand() % 17) is "not good" because it somehow reduces the randomness. I think it was something about dropping the upper bits, but I don't really know anything. Can anybody clarify and elaborate?

Share on other sites
x % (2^y) = x & (2^y) (binary and)

The reson why Rnd % number is considered bad, is because:
IIRC It has a different probablility of being zero, or number then of being something else.

Also, if number and rnd aren't coprime, then gcd((rnd % number), number) will not be 1. IE. they weill hhare at least one factor.

From,
Nice coder

[Edited by - Nice Coder on December 4, 2004 1:52:06 AM]

Share on other sites
Here is an extreme case which demonstrates the problem (which in practice is generally a very small problem).

Suppose MyRand() returns the values 0-9 (inclusive).

Now, you use MyRand to generate random numbers between 0 and 3 (inclusive) and you do it like this:
    v = MyRand() % 4;
Here are the values generated by MyRand() (and their probabilities), and how they map to the final value v:
MyRand():     0   1   2   3   4   5   6   7   8   9probability: 10% 10% 10% 10% 10% 10% 10% 10% 10% 10%MyRand()%3:   0   1   2   3   0   1   2   3   0   1
You can see that v has the values 0 and 1 more often than 2 or 3 (50% more often!).
v:            0   1   2   3probability: 30% 30% 20% 20%

Share on other sites
also lower bits have bad randomness, also, modulo is slow, etc.
I'm using that:
uint32 rseed;const float random_scale_=(1.0/65536.0)*(1.0/65536.0);inline int random(int n){    rseed *= 0x08088405;    rseed += 1 ;    return ((uint64)rseed)*((uint64)((uint32)n))>>32 ;}inline float random(){    rseed *= 0x08088405;    rseed += 1 ;    return (float)(rseed)*random_scale_;}

,mainly for compatibility reasons, but it really works better and is faster. (with free MSVC7.0 compiler, there's no 64 bit multiply in assembler code(i checked), in HW, usual 32 bit multiply have 64 bit result anyway)

[Edited by - Dmytry on December 4, 2004 7:43:07 AM]

1. 1
2. 2
Rutin
18
3. 3
4. 4
5. 5

• 9
• 14
• 9
• 9
• 9
• Forum Statistics

• Total Topics
632920
• Total Posts
3009209
• Who's Online (See full list)

There are no registered users currently online

×