Jump to content
  • Advertisement
Sign in to follow this  
Max_Payne

Pseudo-random Number Generation

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I know there is a method to generate random numbers involving a prime number and a seed. Earlier last year, a CS teacher actually told us about it, and it looked pretty simple. Yet, I can't find how it worked. It worked by performing a simple multiplication, and using the modulo to extract the last bit of the number. Does anybody know what the precise technique is, what is its name, and if its possible to pull out more than one random bit at a time?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Ysaneya
Maybe the Mersenne Twister random number generator ?

Y.


Their source code is quite awful... And I would like to know about the technique, not about this particular variation.

Share this post


Link to post
Share on other sites
Gah, the generator you're looking for is not MT, it's the Quadratic Residue Generator/Blum-Blum-Shub method link. It is very simple and can be implemented in a matter of minutes.

Share this post


Link to post
Share on other sites
Quote:
Original post by jperalta
Gah, the generator you're looking for is not MT, it's the Quadratic Residue Generator/Blum-Blum-Shub method link. It is very simple and can be implemented in a matter of minutes.


Thank you, that seems to be what I am looking for. I still have some questions though.

Supposing I take a fixed M, being the product of two large primes (this is not for cryptographic purposes).

Questions:
1. Is the first X I feed in the system the root?
2. Suppose I do this with 64 bit integers, I have 64 bit M and a 64 bit Xn, does it matter if X*X overflows (is greater than 2^64-1, and thus can't be completely stored in a 64 bit integer).
3. If I always take the 32 least significant bits of Xn+1 as the output, will this give me random numbers, or will it be "not as random" as always taking only one least significant bit?

Share this post


Link to post
Share on other sites
The typical RNG is called an LCG (Linear Congruential Generator). It is extremely simple and relatively fast. It has the the form
    xn+1 = ( xn * a + b ) mod m 
Look up "Linear Congruential Generator" and you will find plenty of suggestions for a, b and m. Here is one:
    uint32 LCG69()
{
seed = seed * 69069 + 1; // note: mod 232 is implicit
return seed;
}
Even though this type of RNG has some drawbacks (notably, the lower bits are not random), it is used extensively. There are other types that are more random or might be more suitable.

Share this post


Link to post
Share on other sites
Blum blum shub looks interesting. Are there any restrictions on what kind of seed you can use to get good results?

Obviously, if you use something like 1 or 0, it won't work right.

Mike C.
http://www.coolgroups.com/zoomer

Share this post


Link to post
Share on other sites
Thanks for bringing up the LCG. That is really what I was looking for. I found some good values and will be implementing a class to handle this and generate both 32 bit and 64 bit random numbers using the same seed (the 32 bit version will just use the 4 high-order bits of the seed).

This is for procedural generation of 3D structures. The reason I am programming it is so that I can be guaranteed to obtain the same values on any machine given the same seed.

Quote:
Original post by mike74
Blum blum shub looks interesting. Are there any restrictions on what kind of seed you can use to get good results?

Obviously, if you use something like 1 or 0, it won't work right.

Mike C.
http://www.coolgroups.com/zoomer


Provided b != 0, I think that the seed 0 will work just fine.

Share this post


Link to post
Share on other sites
Speaking of LCG, i'm using this:

uint32 rseed=123456789;
const float random_scale=(float)( 1.0/((float)((uint32)0xFFFFFFFF)) );
float fast_random()
{
rseed *= 0x08088405;// other prime
rseed += 1 ;
return ((float)rseed)*random_scale;
}




for generating random floats in 0..1 range, and

int fast_random(int i)// returns random number from 0 to i-1
{
rseed *= 0x08088405;// other prime
rseed += 1 ;
return (uint64(rseed)*uint64(i))>>32;// translates into single MUL opcode; on x86, 32 bit multiply gives 64 bit result
}



for generating random integers.

It is method used in Delphi RTL. Generator are not very good but sure is not worse than rand() , and is much faster.

[Edited by - Dmytry on July 19, 2005 9:50:08 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by JohnBolton
The typical RNG is called an LCG (Linear Congruential Generator). It is extremely simple and relatively fast. It has the the form
    xn+1 = ( xn * a + b ) mod m 
Look up "Linear Congruential Generator" and you will find plenty of suggestions for a, b and m. Here is one:
    uint32 LCG69()
{
seed = seed * 69069 + 1; // note: mod 232 is implicit
return seed;
}
Even though this type of RNG has some drawbacks (notably, the lower bits are not random), it is used extensively. There are other types that are more random or might be more suitable.


Thanks Dmytry for clarifying the issue by giving another example of the Linear Congruential Method proposed by JohnBolton we were getting confused here. Is your implementation better than his?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!