Sign in to follow this  

Flexible Random Number Generation

This topic is 4858 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 am using MSVC++ 6, and it doesn't seem to have any libraries included for re-entrant (and more flexible) random number generation. What I need is a random number generator that saves its state in a buffer that I provide for it, such that I can not only have it be re-entrant but also so that I can synchronize random number generation over a Network (by sending this buffer). Any suggestions? I've been searching on google and other places for a while and have had no luck. Thanks, ~SPH EDIT: I would prefer to find a C Implementation, as my project is primarily in C. [Edited by - ShmeeBegek on August 26, 2004 9:41:01 PM]

Share this post


Link to post
Share on other sites
You mean like a simple linear congruence method? Here is a simple implementation.


int prng(int m, int a, int c, int s){
unsigned int x;
x = a*s + c%m;
seed = x;
x = x % 100;
return x;
}


Hope that helps.

[Edit: Wanted to point out that it is not the fastest code, and I dont recommend using it. I made it specifically for my own applications in which time isn't completely of the essence. I recommend writing your own.]

Share this post


Link to post
Share on other sites
Mine is better... but it too is rather slow to compute... it can be synchronized by sending the value of initialSeed over the network. It is a rather non-optimized implementation of the Blum-Blum-Shub pseudo-random bit generator. You could speed it up quite a bit by taking 4-5 of the last bits from each seed number in GetNextRand(). You can increase the maximum size of the number returned by increasing count's limit in the same function.

Note: this assumes that the size of a long is 32-bits and a long long is 64-bits, if your longs are 64-bits just make all the long longs into longs and it'll work nicely.


void InitBBS(long seed);
long long GetNextRand();
long long GetNextCongruence(long long prev);
long FindRelativePrime(long seed,long long n);
long GCD(long long a, long long b);
long long power(long long base, long long exponent);

long long n;
long long initialSeed;

void InitBBS(long seed)
{
long long p = 1031;
long long q = 1051;
n = p * q;

seed = FindRelativePrime(seed,n);

initialSeed = GetNextCongruence(seed);
}

long long GetNextRand()
{
long long retVal = 0;
int count;

for (count = 0; count < 32; count++)
{
initialSeed = GetNextCongruence(initialSeed);
retVal = retVal ^ ((initialSeed % 2)<<count);
}
return retVal;
}

long long GetNextCongruence(long long prev)
{
long long i;

for (i = 0; i < power(prev,2); i++)
{
if ((i % n) == power(prev,2) % n)
return i;
}
}

long long power(long long base, long long exponent)
{
if (exponent == 0)
return 1;
else if (exponent == 1)
return base;
else
return base*power(base,exponent-1);
}

long FindRelativePrime(long seed,long long n)
{
int i;

for (i = seed; i < n; i++)
{
if (GCD(n,i) == 1)
return i;
}
}

long GCD(long long a, long long b)
{
long long temp = 0;
long long r = 0;

if (b > a)
{
temp = a;
a = b;
b = temp;
}

r = a % b;

if (r == 0)
return b;
else
return GCD(b, r);
}





[Edited by - jperalta on August 27, 2004 12:58:07 AM]

Share this post


Link to post
Share on other sites
What if you generate a random number, store it, or generate an array of random numbers and store it.
Then the next time you need to get another random number, instead of calling the rand funtion, you first seed it with the last random number and then you call the rand funtion.
In the case of an array you could xor all the elements, seed the rand funtion with it, and then return another array.

The seed before each random number generation it's because you need to store the state, if you just use the rand funtion, there is no way of passing the state over a network, unless you make your own rand funtion. This way, the random number you generate IS the state.

Hope it helps. =)

Share this post


Link to post
Share on other sites
I may be wrong, but when you need to do the synchronization check, could you not just use the current RNG to choose a seed, use that seed, and send it over the network so the other generators use it too? Then they'll be synchronized. This is probably bad if you need to synchronize often, though.

Share this post


Link to post
Share on other sites
Quote:
Original post by ShmeeBegek
I was actually hoping for a C implementation, I'll edit my post to include this.


You could wrap boost in a C API and put it in a library.

Share this post


Link to post
Share on other sites
Quote:
Original post by ShmeeBegek

I was actually hoping for a C implementation, I'll edit my post to include this.

Thanks, ~SPH


If the standard library's rand () suits your purpose, just copy the source and modify it to use an external variable instead of a static.

For MS VS.NET, rand () is:

/***
*int rand() - returns a random number
*
*Purpose:
* returns a pseudo-random number 0 through 32767.
*
*Entry:
* None.
*
*Exit:
* Returns a pseudo-random number 0 through 32767.
*
*Exceptions:
*
*******************************************************************************/


int __cdecl rand (
void
)
{
#ifdef _MT

_ptiddata ptd = _getptd();

return( ((ptd->_holdrand = ptd->_holdrand * 214013L
+ 2531011L) >> 16) & 0x7fff );

#else /* _MT */
return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
#endif /* _MT */
}



So just create a function like the following:

int re_rand (int *holdrand)
{
return(((*holdrand = *holdrand * 214013L + 2531011L) >> 16) & 0x7fff);

// Just add a rand_state variable to any structure that needs
// its own random numbers and call re_rand using that
typedef struct
{
int health;
int attack;
int defense;
int randState;
} BadGuy;

BadGuy b;

// do some attack w/ bad guy
int damage = b.attack * re_rand (&b.randState) / (RAND_MAX+1);

// synchronize w/ network
int seed = getNetworkSeed ();
b.randState = seed;
}



**flamebait retardant**: I'm well-aware of the shortfalls of MS's version of rand; this is merely to show how to change a function that uses globals into a re-entrant function.

Share this post


Link to post
Share on other sites
i'm using

// return value is in range 0..n-1
// No divide needed(% is as costly as divide)
inline int random(int n,uint32 &rseed)//minor fix for case we're on 64 bit system
{
rseed *= 0x08088405;
rseed += 1 ;
return ((uint64)((uint32)rseed))*((uint64)((uint32)n))>>32 ;
}






it's standard generator used in Borland Delphi.I heard it's not very very good(anyway,most programs will not notice) but it's VERY fast(assuming your compiler will optimize thing that "looks like 64 bit multiply" to single "mul" opcode (on x86, normal 32 bit multiply gives 64 bit result.) MSVC .net optimizes it well. )

uint32 and uint64 is a unsigned 32 and 64 bit integers.

[Edited by - Dmytry on August 28, 2004 1:13:10 AM]

Share this post


Link to post
Share on other sites
I still maintain that my random number generator will generate the most random numbers. The BBS system, while slow, is better than any form of LFSR/GFSR, even when you take 4 bits from each number, rather than 1, and when you take 4 bits from each number it only takes about 1 second to generate a number.

Share this post


Link to post
Share on other sites
Quote:
Original post by jperalta
I still maintain that my random number generator will generate the most random numbers. The BBS system, while slow, is better than any form of LFSR/GFSR, even when you take 4 bits from each number, rather than 1, and when you take 4 bits from each number it only takes about 1 second to generate a number.
Of course, simple Linear Congruence generators are good enough for just about everything, and the Mersenne Twister has you beat (both in 'randomness' and most probably speed as well, but its state is rather large).

Edit: I'm going to have to disagree with you about the BBS system entirely. I don't know PRNG theory well, but it looks like a rather poor algorithm. You're reducing the period by a factor of 32 since you're generating one number per bit using a single seed, plus it goes to a lot of trouble to initialize the seed to itself (unless it is a multiple of P or Q, which could be tested with two conditional statements).
There are a few other 'intereting' details but I'm too tired to really examine the code and like I said I really don't know PRNG theory so I could be completely wrong.

Share this post


Link to post
Share on other sites
My implementation is pretty poor, but I'm not 100% sure you actually have to test to generate the relative prime because as I recall if you have primes p and q and n = p*q then any number m != p & != q should be relatively prime to n.

Edit: Yeah, that's right, I should actually take the call to FindRelativePrime() and just fail if the user gives p or q as the seed or if the GCD between n and seed != 1, but that can only occur if seed > n and n|seed which is a very unlikely situation.

[Edited by - jperalta on August 27, 2004 7:24:24 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by ShmeeBegek
I am using MSVC++ 6, and it doesn't seem to have any libraries included for re-entrant (and more flexible) random number generation.
Take a look at the CryptGenRandom() function. It generates cryptographically strong pseudo-random numbers in the form of a byte array.
#include <windows.h>
#include <wincrypt.h>
...
static HCRYPTPROV hProv;
result = CryptAcquireContext(&hProv, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT);
...
unsigned int randomNumber;
result = CryptGenRandom(hProv, sizeof(int), (unsigned char*)&randomNumber);
...
result = CryptReleaseContext(hProv, 0);

Share this post


Link to post
Share on other sites

This topic is 4858 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.

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