Date: Sat, 5 Oct 1996 21:15:05 +1000 From: Bruce Evans <bde@zeta.org.au> To: ache@nagual.ru, joerg_wunsch@uriah.heep.sax.de Cc: current@FreeBSD.org, freebsd-hackers@FreeBSD.org Subject: Re: I plan to change random() for -current (was Re: rand() and random()) Message-ID: <199610051115.VAA21012@godzilla.zeta.org.au>
next in thread | raw e-mail | index | archive | help
>> I don't think so. But they are much better with random(). See xmine,
>> if you wanna get a nice example. It generates totally predictable
>> layouts when using rand().
>
>Totally predictable layouts not rand() illness only but random() too.
>It not depends well on different initial state, producing the same
>sequence. I finally dig out initial posting (below).
It says that the 0th bit is the most non-random. In fact, it is obvious
from the formula for rand() that
(rand() & 1) == previous_value_returned_by_rand ^ 1
:-(.
The posting also says that the bad values for rand() make the seeding
for random() bad. This seems reasonable.
>IMHO we need to change our random() as suggested.
How do you know that the suggested method is better?
---
>From: warwick@cs.uq.edu.au (Warwick Allison)
>...
>warner@rmcs.cranfield.ac.uk (Alistair (Joe) Warner) writes:
>
>> BSD: state[i] = 1103515245 * state[i - 1] + 12345;
>> Linux: state[i] = 1103515145 * state[i - 1] + 12345;
ISO C example: next = 1103515245 * next + 12345;
return (unsigned int)(next / 65536) % 32768;
I.e., it returns bits 16-31 of the current state (right shifted 16). This
is said to be better. Folklore says that someone broke rand() by not
discarding the low bits when ints became 32 bits.
>value will make NO DIFFERENCE. The change I give below is of the type
>required for success.
>
>
>#include <stdlib.h>
>
>#define LOOP 200
>#define ITER 200
>
>main()
>{
> int s=time(0);
> int i,l,m,j;
>
> int seed=0;
>
> printf("P1\n%d %d\n",ITER,LOOP);
> for (l=0; l<LOOP; l++) {
> srandom(seed); seed+=1;
> for (i=0; i<ITER; i++) {
> int b=(random()>>8)&1; /* remove >>8 for WORSE */
> printf("%d\n",b);
> }
> }
>}
Similarly for rand(). You can throw away the lowest 16 bits yourself
to get a rand() no worse than the example in the ISO C standard. This
is said to be bad, but I think the badness is more in the brokenness as
specified (the number of starting states is limited by the srand()
interface) and in the limited period (which is inherent in the LCRNG
implementation) than in the coefficients for the LCRNG.
>>To: bug-glibc@prep.ai.mit.edu
>>cc:
>>Subject: PARTIAL FIX FOR: srandom() in libc
>--------
>...
>Nothing can be done to change the EXTREME uniformity of the resulting
>image, as the code in srandom() makes a fundamental mistake: it uses a
>power of two as the modulo which is mathematically a `poor' choice.
>Code I suggest is better uses the largest 31-bit prime (2^31-1), which
>is a `good' choice mentioned in the literature (I can find references,
>if that would be useful) - the image resulting from the above is then
According to Knuth, moduli of the form 2^n+1 and 2^n-1 have the advantage
that the low order bits are just as random as the high order ones.
However, "In most applications, the low-order bits are insignificant,
and the choice m=w [modulus = 2^n] is quite satisfactory - provided the
programmer using the random numbers does so wisely". In the ISO example,
it is actually an advantage to have randomness concentrated in the high
order bits (is it?). ISO only guarantees 16 bit integers, so a portably
example can only return 15 bits of randomness, so the low bits are not
useful; OTOH, longs have to be used to get a reasonably large period -
16 bit ints are too small.
>! /*
>! * Implements the following, without overflowing 31 bits:
>! *
>! * state[i] = (16807 * state[i - 1]) % 2147483647;
>! *
>! * 2^31-1 (prime) = 2147483647 = 127773*16807+2836
>! */
>! long int hi = state[i-1] / 127773;
>! long int lo = state[i-1] % 127773;
>! long int test = 16807*lo - 2836*hi;
>! state[i] = test + (test<0 ? 2147483647 : 0);
This method is also found in the BSD4.4Lite libkern/rand.c. I guess it
can be trusted (as much as the BSD rand.c :-).
Bruce
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199610051115.VAA21012>