Sign in to follow this  
Promit

Psuedo-random number generators and modulo

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 this post


Link to post
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.

Thats about as much as i know about this.
From,
Nice coder

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

Share this post


Link to post
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   9
probability: 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   3
probability: 30% 30% 20% 20%

Share this post


Link to post
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]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this