Sign in to follow this  
Max_Payne

Pseudo-random Number Generation

Recommended Posts

Max_Payne    757
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
jperalta    356
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
Max_Payne    757
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
JohnBolton    1372
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
mike74    100
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
Max_Payne    757
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
Dmytry    1151
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
jovani    100
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
Dmytry    1151
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 this post


Link to post
Share on other sites
Max_Payne    757
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 this post


Link to post
Share on other sites
mattnewport    1038
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.

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