Flexible Random Number Generation
Author
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]
Author
I was actually hoping for a C implementation, I'll edit my post to include this.
Thanks, ~SPH
You mean like a simple linear congruence method? Here is a simple implementation.
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.]
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.]
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.
[Edited by - jperalta on August 27, 2004 12:58:07 AM]
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]
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. =)
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. =)
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.
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.
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 thattypedef struct{ int health; int attack; int defense; int randState;} BadGuy;BadGuy b;// do some attack w/ bad guyint damage = b.attack * re_rand (&b.randState) / (RAND_MAX+1);// synchronize w/ networkint 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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
