Pseudo-random Number Generation
Author
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?
Author
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.
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.
Author
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?
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 uint32 LCG69() { seed = seed * 69069 + 1; // note: mod 232 is implicit return seed; }
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
Obviously, if you use something like 1 or 0, it won't work right.
Mike C.
http://www.coolgroups.com/zoomer
Author
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.
Provided b != 0, I think that the seed 0 will work just fine.
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.
Speaking of LCG, i'm using this:
for generating random floats in 0..1 range, and
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]
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]
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 formLook up "Linear Congruential Generator" and you will find plenty of suggestions for a, b and m. Here is one:xn+1 = ( xn * a + b ) mod mEven 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.uint32 LCG69() { seed = seed * 69069 + 1; // note: mod 232 is implicit return seed; }
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?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
