Mail Archives: djgpp-workers/2000/06/09/08:18:59
DJ Delorie wrote:
> Could those of you with random number generator testers compare these
> generators? The first is from DJGPP, and the other two are from
> newlib.
All three are linear congruential generators. The nth random number
is
x_n = (x_{n-1}*a + b) % c
where in the first case additionally the low bits are discarded.
> #define RAND_MAX 0x7fffffff
>
> unsigned
> rand1()
> {
> static unsigned long long next = 1;
> next = next * 6364136223846793005LL + 1;
> return (int)((next >> 21) & RAND_MAX);
> }
I have allready commented on this. It will fail some tests. Using a
shift of 32 (or 33), will improve this much. But it has the
weaknesses of all LCGs with a modulus of 2^N (here N is 64).
> unsigned
> rand2()
> {
> long k;
> static long s = 1;
> if (s == 0)
> s = 0x12345987;
> k = s / 127773;
> s = 16807 * (s - k * 127773) - 2836 * k;
> if (s < 0)
> s += 2147483647;
> return (int)(s & RAND_MAX);
The mask is not needed here. This RNG should have RAND_MAX defined
as 0x7ffffffe. It will never return 0x7fffffff.
> }
This is an implementation of the Park and Miller minstd. (I think
it's from the paper cited in the FAQ.) It is equivalent to
x_n = ( x_{n-1} * 16807) % 2147483647,
so it is essentially just two lines of inline assembly.
This is about as good, as you can get for a LCG with a 31bit state.
(Note, that 2147483647 = 2^31-1 is a prime). But because of the
limited period, it will fail some tests.
> unsigned
> rand3()
> {
> static unsigned int next = 1;
> return ((next = next * 1103515245 + 12345 ) & RAND_MAX );
> }
This is a very inferior PRNG. It will fail almost all tests. I.e. the
LSB will just toggle between 0 and 1.
I have test logs of all of those. If you're interested, I can send
them to you.
- Raw text -