[Freeciv-Dev] Re: Random generator not random at all

[Falk Hueffner <falk.hueffner@xxxxxxxxxxxxxxxxxxxxxxxx>]

Jarda Benkovsky <pvt.benkovsk@xxxxxxxxx> writes:

> this is a sequence of results you usually get (or s.t. similar)  when
> you call myrand(2) repeatedly:
> 
> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
> 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,
> 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,
> 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
> 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1,
> 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1,
> 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
> 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,
> 1, 0, 1, 0, 1, 0, 1, 0, 
> 
> It does not look good, I am afraid :(
> 
> For bigger values of argument to myrand() the results look better, but
> ...
> I have stumbled upon this when trying to find out why some nations are
> suggested often and others are not. Of course, this sequence could be
> found really random when looking at 1E6 calls, but somehow I doubt it :)

ARGH it uses % to reduce the space. This is about the first thing one
lears about RNGs... To cite rand(3) on Linux:

       In Numerical Recipes in C: The Art of Scientific Computing
       (William  H.  Press, Brian P. Flannery, Saul A. Teukolsky,
       William T.  Vetterling;  New  York:  Cambridge  University
       Press,  1992 (2nd ed, p. 277)), the following comments are
       made:
              "If you want to generate a random integer between 1
              and 10, you should always do it by using high-order
              bits, as in

                     j=1+(int) (10.0*rand()/(RAND_MAX+1.0));

              and never by anything resembling

                     j=1+(rand() % 10);

              (which uses lower-order bits)."


So myrand should probably return (int) ((double) size * new_rand / MAX_UINT32).

I've done a few tests, and it seems the RNG gets a lot bette after a
while, while the first few 1000 numbers are really bad (I used
time(NULL) as seed, like freeciv does). So in any case it would be a
good idea to "heat it up" before each use by generating 100000 random
numbers.

A test that reveals the low quality is:

    int i, old = 0, new;
    int didchange, olddidchange;
    int behaviourchange = 0, behavioursame = 0;

    mysrand(time(NULL));

    for (i = 0; i < 100; ++i) {
        new = myrand(2);
        didchange = (new != old);

        if (didchange != olddidchange)
            ++behaviourchange;
        else
            ++behavioursame;

        olddidchange = didchange;
        old = new;
    }
    printf("\nsame: %d, change: %d\n", behavioursame, behaviourchange);

With real numbers, behaviourchange and behavioursame should be about
the same size.

        Falk