gcc rand() failures: lengthy post justified?
George Marsaglia
Wai Wan Tsang and staff at Computer Science
and Information Systems at The University of
Hong Kong, we are about to release a new version of
The Diehard Battery of Tests of Randomness,
which will be available from a web site there.
(You may want to watch for it. I will post
details in a few days.)
In a trial of the procedure, I just downloaded
the C files and compiled them with gcc on djgpp for DOS.
I then tried the tests on that gcc's rand() function.
I have seldom seen a RNG that performs so poorly on
tests of randomness.
There may be users of gcc who would be interested
in the results, but the full battery of tests would take
about 19 screenfuls to display. The display would
also give an idea of the new version's layout.
Is it proper to post such a lengthy message to a
newsgroup such as this?
If it were, I would.
I do not want to be bothered to send emails to each
who might be interested.
George Marsaglia
Daniel Fox
jXT...@comcast.com:
> In cooperation with my colleague Professor
> Wai Wan Tsang and staff at Computer Science
> and Information Systems at The University of
> Hong Kong, we are about to release a new version of
> The Diehard Battery of Tests of Randomness,
> which will be available from a web site there.
> (You may want to watch for it. I will post
> details in a few days.)
>
> In a trial of the procedure, I just downloaded
> the C files and compiled them with gcc on djgpp for DOS.
> I then tried the tests on that gcc's rand() function.
Maybe your colleague Professor Wai Wan Tsang can help you learn about the
difference between a compiler and a C Standard Library implementation.
DJGPP may use the GNU gcc compiler, but DJGPP's implementation of the C
Standard Library including the rand() function was done by DJ Delorie and
has nothing to do with gcc itself.
That DJGPP's rand() is suboptimal isn't big news. Anyone who cares to
examine the source will see that it isn't exactly complex:
int
rand(void)
{
/* This multiplier was obtained from Knuth, D.E., "The Art of
Computer Programming," Vol 2, Seminumerical Algorithms, Third
Edition, Addison-Wesley, 1998, p. 106 (line 26) & p. 108 */
next = next * 6364136223846793005LL + 1;
return (int)((next >> 21) & RAND_MAX);
}
> There may be users of gcc who would be interested
> in the results, but the full battery of tests would take
> about 19 screenfuls to display. The display would
> also give an idea of the new version's layout.
>
> Is it proper to post such a lengthy message to a
> newsgroup such as this?
No. Please don't.
- Daniel
Tars_Tarkas
> "George Marsaglia" <g...@stat.fsu.edu> wrote in news:irGcnWUAT5fLy9-
> jXT...@comcast.com:
>
>>There may be users of gcc who would be interested
>>in the results, but the full battery of tests would take
>>about 19 screenfuls to display. The display would
>>also give an idea of the new version's layout.
>>
>>Is it proper to post such a lengthy message to a
>>newsgroup such as this?
>
>
> No. Please don't.
What you could do though, is make a little webpage (even if it's only
the output of the tests) and post the url of that. Not sure if this is
the right newsgroup for it though, the test output for gcc I mean...
--
GP_Spukgestalt, human C coder, killed by the RNG.
George Marsaglia
"Daniel Fox" <danielfox200...@hotmail.com> wrote in message
news:Xns931A504F97C8E...@65.82.44.187...
> Maybe your colleague Professor Wai Wan Tsang can help you learn about the
> difference between a compiler and a C Standard Library implementation.
> DJGPP may use the GNU gcc compiler, but DJGPP's implementation of the C
> Standard Library including the rand() function was done by DJ Delorie and
> has nothing to do with gcc itself.
>
> That DJGPP's rand() is suboptimal isn't big news. Anyone who cares to
> examine the source will see that it isn't exactly complex:
>
> int
> rand(void)
> {
> /* This multiplier was obtained from Knuth, D.E., "The Art of
> Computer Programming," Vol 2, Seminumerical Algorithms, Third
> Edition, Addison-Wesley, 1998, p. 106 (line 26) & p. 108 */
> next = next * 6364136223846793005LL + 1;
>
> return (int)((next >> 21) & RAND_MAX);
> }
I did not know the source of rand() on gcc for djgpp,
and appreciate your information, although not the
insult you apparently intended when providing it.
Clipping of bits from a congruential RNG may improve, or
may make worse the suitability of the bits that remain.
I was surprised at how bad that particular rand() function
was, and others may want to know details, despite
your opinion "That DJGPP's rand() is suboptimal isn't big news".
I wonder if such news, little or big, is well known to potential users.
Perhaps you could provide more detail, or justify your
implication that a good RNG must be complex.
That aside, my purpose in this response is positive:
the site for the new version of the Diehard battery of tests
is now available at
www.csis.hku.hk/~diehard
I only learned of it this morning, and your speedy response
to my original query made it possible to provide the update.
Interested readers may want to download the tests and
apply them to RNG 's they use with C, or to files of
purported random bits.
George Marsaglia
Dan Pop
>In a trial of the procedure, I just downloaded
>the C files and compiled them with gcc on djgpp for DOS.
>I then tried the tests on that gcc's rand() function.
There is no such thing as gcc's rand() function. gcc is a compiler and
rand() is a standard library function. gcc typically uses the libraries
already available on the underlying platform.
>I have seldom seen a RNG that performs so poorly on
>tests of randomness.
It is no big news that most rand() implementations sacrifice quality to
speed. The C standard itself provides this sample implementation:
static unsigned long int next = 1;
int rand(void) /* RAND_MAX assumed to be 32767 */
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
void srand(unsigned int seed)
{
next = seed;
}
and (far too) many implementations just use it. You can easily tell,
by looking at the value of RAND_MAX, which has no reason to be 32767
on a 32-bit (or wider) platform.
Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Dan...@ifh.de
Daniel Fox
>
> "Daniel Fox" <danielfox200...@hotmail.com> wrote in message
> news:Xns931A504F97C8E...@65.82.44.187...
> I did not know the source of rand() on gcc for djgpp,
> and appreciate your information, although not the
> insult you apparently intended when providing it.
I was attempting to point out the fact that gcc and the implementation of
rand() that you're concerned about aren't necessarily related any more than
the fact that they are used together. Your subject line implies there's a
fault in gcc in that regard; there is not. However, I do apologize for the
tone of my response, although no personal insult was intended.
> Clipping of bits from a congruential RNG may improve, or
> may make worse the suitability of the bits that remain.
> I was surprised at how bad that particular rand() function
> was, and others may want to know details, despite
> your opinion "That DJGPP's rand() is suboptimal isn't big news".
If someone is concerned about the quality of the numbers rand() is spitting
out, then they probably will want to examine the source creating them,
which in this case is freely available. Isn't examination of the source
standard procedure when doing this sort of analysis?
> I wonder if such news, little or big, is well known to potential
> users. Perhaps you could provide more detail, or justify your
> implication that a good RNG must be complex.
That rand() can be dodgy at best on many platforms is well known on
comp.lang.c. I wasn't attempting to publish a thesis corrolating code
complexity with entropy, but I think its fairly clear that you're not going
to wind up with a cryptographic quality RNG out of two lines of C code that
smell awfully like the poor version given in the C standard that haunted C
libraries for a while.
Perhaps DJ should have used 69069 as the multiplier. I hear its the best of
all multipliers ;)
- Daniel
Martin Dickopp
> I think its fairly clear that you're not going to wind up with a
> cryptographic quality RNG out of two lines of C code that smell awfully
> like the poor version given in the C standard that haunted C libraries for
> a while.
Here is a two line implementation of the Blum-Blum-Shub generator, a
cryptographically strong pseudorandom bit stream generator. ;-)
#define N (251 * 239) /* must be product of two primes which are
congruent to 3 modulo 4 */
#define SEED 7 /* must be relatively prime to N */
static unsigned int value = SEED;
unsigned int random_bit (void)
{
value = ((unsigned long)value * value) % N;
return value & 1;
}
Martin
George Marsaglia
"Martin Dickopp" <firefl...@gmx.net> wrote in message
news:b1u95i$h74$05$1...@news.t-online.com...
Interesting. As I was testing the new download of Diehard at
www.csis.hku.hk\~diehard
I tried this version of your suggestion, using two larger primes,
but keeping their product <2^32 to ensure the gcc I use would work:
unsigned int randbit(void){
unsigned long long N=3444437417LL; // N=60943*56519
static unsigned long long x=1234567;
x=(x*x)%N;
return x&1; }
I made a stream of 2,147,483,673 bits from randbit() and subjected it to
the Diehard battery. It seemed as bad as rand(), although badness
is hard to quantify.
You might want to try it yourself .
It failed, spectacularly, all the Monkey tests, which are concerned with
the frequency of various bit patterns in the stream, the gcd test,
the count-the-1's in a byte, the squeeze test, and could not be used to
play a satisfactory game of craps. But it is pretty good at choosing a
random birthday in a year of 2^32 days.
The summary of all the p-values for the tests, a new feature of Diehard,
is:
0.7758,0.4687,0.9211,0.1773,0.7493,0.7433,0.7399,0.6148,0.9079,0.0839,
0.5796,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,0.0475,0.6792,0.8608,0.7497,0.0675,0.3880,0.4434,0.2026,0.7936,
0.7073,0.0943,0.4836,0.4997,0.3452,0.8333,0.7815,0.1985,0.4563,0.5123,
0.5068,0.7905,0.7826,0.1633,0.3736,0.4151,0.3814,0.7829,0.4452,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,0.1928,0.7081,0.7387,
0.5364,0.6079,0.4097,0.5903,0.2188,0.6079,0.4275,0.3700,0.5573,0.5124,
0.0428,0.1383,0.9114,0.9105,0.2828,0.4263,0.2078,0.8566,0.9438,0.3848,
0.2992,0.5617,0.5799,0.8345,0.7506,0.9023,0.1140,0.2849,0.4745,0.3564,
0.3214,0.2037,0.7386,0.7510,0.5817,0.9025,0.7600,0.1035,0.3926,0.7721,
1.0000,0.1260,0.6144,0.6084,0.6541,0.0065,0.0969,0.1539,0.0109,0.2487,
0.4386,0.0215,1.0000,0.9979,0.9792,0.7617,1.0000,0.8576,1.0000,
while those for rand() were
1.0000,0.9334,0.1012,0.8210,0.9260,0.9684,0.9165,0.7954,0.9182,0.0000,
1.0000,1.0000,0.8937,1.0000,0.8775,0.3339,0.3039,0.1491,0.9952,0.2557,
0.6968,0.3194,0.0561,0.2826,0.1751,0.4341,0.2426,0.5065,0.8801,0.3282,
0.5073,0.0421,0.8561,0.3426,0.0000,0.0000,0.0000,0.0000,0.0000,0.0000,
0.0000,1.0000,1.0000,1.0000,1.0000,1.0000,0.8354,0.4834,0.8819,0.1950,
0.6809,1.0000,1.0000,1.0000,0.8272,0.3987,0.9888,0.9449,0.5988,0.8709,
0.6104,0.0301,0.0108,0.1774,0.4636,0.9726,0.9028,0.4963,0.7736,0.5715,
0.7217,0.6571,0.3319,0.0210,0.8756,0.5459,0.0928,0.6674,0.0202,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,
1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,1.0000,0.6280,
0.0602,0.0864,0.1950,0.7149,0.5023,0.7756,0.6319,0.9099,0.3699,0.9231,
0.7673,0.9576,0.8840,0.6422,0.2831,0.0765,0.6588,0.3962,0.2247,0.9530,
0.7138,1.0000,0.0000,0.0001,0.0022,0.0609,0.0733,0.2276,0.1642,0.3720,
0.9495,0.6271,0.1934,0.5185,0.6760,0.9021,0.0935,0.6674,0.2327,0.6917,
0.3517,0.1202,0.4045,0.0597,0.5090,0.3771,0.6674,0.5225,0.8955,1.0000,
0.0185,1.0000,0.8883,1.0000,1.0000,1.0000,1.0000,1.0000,0.9301,0.4375,
0.9813,0.3298,0.0617,0.6357,0.1761,0.3077,0.4714,0.3395,0.2041,0.0471,
0.8711,0.1627,0.6620,0.9265,0.1206,0.4784,0.7556,0.1037,0.7425,0.0665,
1.0000,1.0000,1.0000,0.6864,0.6994,0.5411,0.7167,0.1131,0.8134,0.3823,
0.4273,0.2330,0.4702,0.6199,0.6610,0.3201,0.5541,0.4229,0.1743,0.8928,
0.5074,0.3141,0.3286,0.1573,0.7109,0.2958,0.9107,0.0000,0.0000,0.0000,
0.0000,0.0000,0.0000,0.0000,0.0000,0.0000,0.0000,0.0000,0.2026,0.0431,
0.2978,0.4992,0.0411,0.3682,0.2775,0.1785,0.3746,0.0728,0.0053,0.1591,
0.2369,0.0943,0.0677,0.1416,0.0899,0.1416,0.0528,0.2641,0.0684,0.0244,
0.1402,0.0161,0.1550,0.0185,0.3397,0.1559,0.2886,0.1602,0.1904,0.0000,
1.0000,0.0000,0.0000,0.0000,0.0000,0.0000,0.0000,0.0000,0.0000,0.0000,
0.0000,0.0000,0.1693,0.0657,0.5041,1.0000,1.0000,0.7833,0.6398,
George Marsaglia
Martin Dickopp
> "Martin Dickopp" <firefl...@gmx.net> wrote in message
> news:b1u95i$h74$05$1...@news.t-online.com...
>
> > Here is a two line implementation of the Blum-Blum-Shub generator, a
> > cryptographically strong pseudorandom bit stream generator. ;-)
> >
> > #define N (251 * 239) /* must be product of two primes which are
> > congruent to 3 modulo 4 */
> > #define SEED 7 /* must be relatively prime to N */
> >
> > static unsigned int value = SEED;
> >
> > unsigned int random_bit (void)
> > {
> > value = ((unsigned long)value * value) % N;
> > return value & 1;
> > }
>
> Interesting. As I was testing the new download of Diehard at
> www.csis.hku.hk\~diehard
> I tried this version of your suggestion, using two larger primes,
> but keeping their product <2^32 to ensure the gcc I use would work:
>
> unsigned int randbit(void){
> unsigned long long N=3444437417LL; // N=60943*56519
> static unsigned long long x=1234567;
> x=(x*x)%N;
> return x&1; }
>
> I made a stream of 2,147,483,673 bits from randbit() and subjected it to
> the Diehard battery. It seemed as bad as rand(), although badness
> is hard to quantify.
With your choice of modulus, the generator has a period length of 265,350,
so you have generated the same bit sequence more than eight thousand times.
In real cryptographic applications, a *much* larger modulus is used.
The Blum-Blum-Shub generator is also too slow to be appropriate as a general
purpose PRNG. Cryptographers use it because it has some *provable* mathe-
matical properties, of which the most important is that by looking at its
output alone, there is no better than 50% chance to guess what the next bit
will be (as long as the period length is not exceeded).
But this is off-topic here. If you are interested in more details, ask in
sci.crypt (after reading their FAQ).
Martin
pete
> Interesting. As I was testing the new download of Diehard at
> www.csis.hku.hk\~diehard
Have you seen the Mersenne Twister ?
http://www.math.keio.ac.jp/~matumoto/cokus.c
--
pete
Eric Sosman
Um, er, it seems a pretty good bet that George
Marsaglia has greater than average familiarity with
developments in the arena of random numbers ...
comp.lang.c will next teach C to Dennis Ritchie,
floating-point arithmetic to William Kahan, and theology
to the Pope.
Jirka Klaue
No, theology is off-topic in comp.lang.c. ;-)
Jirka
Tak-Shing Chan
> pete wrote:
>>
>> George Marsaglia wrote:
>>> www.csis.hku.hk\~diehard
>>
>> Have you seen the Mersenne Twister ?
>
> Um, er, it seems a pretty good bet that George
> Marsaglia has greater than average familiarity with
> developments in the arena of random numbers ...
Even ``pretty good bet'' is an understatement, as you
already know. I would change it to ``with probability 1''.
Tak-Shing
Joona I Palaste
With any luck the next thing we will teach is democracy to George W.
Bush. Of the five listed above, he's the one in the most desperate need
of teaching.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"Shh! The maestro is decomposing!"
- Gary Larson