# Pseudo-random Number Generation

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

## 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 on other sites
Maybe the Mersenne Twister random number generator ?

Y.

##### Share on other sites
Quote:
 Original post by YsaneyaMaybe the Mersenne Twister random number generator ?Y.

##### 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 on other sites
Quote:
 Original post by jperaltaGah, 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 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 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 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 mike74Blum 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 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 on other sites
Quote:
 Original post by JohnBoltonThe 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?

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633293
• Total Posts
3011237
• ### Who's Online (See full list)

There are no registered users currently online

×