# Pseudo-random Number Generation

## 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?

##### Share on other sites
Isn't it useful to show example of LCG using different prime number? Isn't it hard to read beginning, "Speaking of LCG,"
In rather unlikely case that he uses random numbers in such way that one of these methods looks visually non-random (he needs it to make 3D structures), other could quite likely look random (and vice-versa)

##### Share on other sites
I just quickly coded my own LCG random number generator class with portability in mind:

random.h:
typedef unsigned long long int uint64;typedef unsigned long int uint32;typedef double float64;typedef float float32;class CRandomGenerator{public:    // Constructor and destructor    CRandomGenerator() {}   ~CRandomGenerator() {}    // Method to set a 32bit random seed    void SetSeed(uint32 Seed);    // Method to compute a 64bit random integer    uint64 RandomInt64();    // Method to compute a 32bit random integer    uint32 RandomInt32();    // Method to compute a 64bit random float    float64 RandomFloat64();    // Method to compute a 32bit random float    float32 RandomFloat32();private:    // Constants for 64 bit random values    // Xn+1 = A * Xn + B (mod 2^64)    static const uint64 A_CONSTANT_64 = (uint64)(0x27BB2EE6)*(0x010000)*(0x010000) + (uint64)(0x87B0B0F);    static const uint64 B_CONSTANT_64 = 0xB504F32D;    // Constants for 32 bit random values    // Xn+1 = A * Xn + B (mod 2^32)    static const uint32 A_CONSTANT_32 = 0x0019660D;    static const uint32 B_CONSTANT_32 = 0x3C6EF35F;    // Maximum integer values    static const uint64 MAX_INT_64 = (uint64)(0xFFFFFFFF)*(0x010000)*(0x010000) + (uint64)(0xFFFFFFFF);    static const uint32 MAX_INT_32 = (uint32)(0xFFFFFFFF);    // Scaling values for random float generations    static const float64 FLOAT_SCALE_64 = (float64)1.0 / (float64)MAX_INT_64;    static const float32 FLOAT_SCALE_32 = (float32)1.0 / (float32)MAX_INT_32;      // Random seed    union Seed    {        uint64 Int64;        uint32 Int32;    } m_Seed;};

random.cpp:
#include "random.h"void CRandomGenerator::SetSeed(uint32 Seed){    m_Seed.Int64 = 0;    m_Seed.Int32 = Seed;}uint64 CRandomGenerator::RandomInt64(){    m_Seed.Int64 = m_Seed.Int64 * A_CONSTANT_64 + B_CONSTANT_64;    return m_Seed.Int64;}uint32 CRandomGenerator::RandomInt32(){    m_Seed.Int32 = m_Seed.Int32 * A_CONSTANT_32 + B_CONSTANT_32;    return m_Seed.Int32;}float64 CRandomGenerator::RandomFloat64(){    return (float64)RandomInt64() * FLOAT_SCALE_64;}float32 CRandomGenerator::RandomFloat32(){    return (float32)RandomInt32() * FLOAT_SCALE_32;}

Test code:
#include <iostream>#include "random.h"int main(int argc, char** argv){    CRandomGenerator RandomGenerator;    RandomGenerator.SetSeed(1337);    uint32 NumValues = 1000000;    float32 Sum = 0.0f;    for (uint32 i = 0; i < NumValues; ++i)    {        Sum += RandomGenerator.RandomFloat32();    }    std::cout << "Float: " << RandomGenerator.RandomFloat32() << std::endl;    std::cout << "Average: " << Sum / NumValues << std::endl;    float64 Sum64 = 0.0;    for (uint32 i = 0; i < NumValues; ++i)    {        Sum64 += RandomGenerator.RandomFloat64();    }    std::cout << "Double: " << RandomGenerator.RandomFloat64() << std::endl;    std::cout << "Average: " << Sum64 / NumValues << std::endl;    return 0;}

Test output:
Float: 0.939825
Average: 0.500492
Double: 0.721694
Average: 0.499735

It seems to be working right. It generates floats between 0 and 1, and their average converges to 0.5 because they are uniformly distributed. If you are wondering about the weird hexadecimal stuff, its because I can't directly write 64 bit integers in GCC. Hence I have to write it out in two 32 bit parts, multiply one of them by 2^32 and take their sum to obtain the whole number. I did not use bit shifting because its meaning could be different on other (big endian) platforms.

##### Share on other sites
You have to be a bit careful with using LCGs for graphics. I've seen pretty visible artifacts in procedural textures where the non-random distributions produced by many simple PRNGs start showing up. The human visual system is very sensitive to certain kinds of patterns and many PRNGs have a tendency to produce quite non-uniform distributions in 2 or 3 dimensions. If everything looks fine then stick with what works but if you start seeing peculiar artifacts you might want to try varying the generator you use.

## Create an account

Register a new account

• ## Partner Spotlight

• ### Forum Statistics

• Total Topics
627684
• Total Posts
2978627

• 9
• 14
• 12
• 10
• 12