BUG #12589: Poor randomness from random() with some seeds; poor resolution

The following bug has been logged on the website:

Bug reference:      12589
Logged by:          Pedro Gimeno
Email address:      pgsql-004@personal.formauri.es
PostgreSQL version: 9.1.13
Operating system:   Debian Wheezy
Description:

postgres=> select version();
                                        version

----------------------------------------------------------------------------------------
 PostgreSQL 9.1.13 on i686-pc-linux-gnu, compiled by gcc (Debian 4.7.2-5)
4.7.2, 32-bit
(1 row)

postgres=> select setseed(1);
 setseed
---------

(1 row)

postgres=> -- formatted as array for compactness of output in email
postgres=> select array(select floor(random()*40) from generate_series(1,
40));
                                                         ?column?


---------------------------------------------------------------------------------------------------------------------------


{19,39,19,19,39,19,39,39,39,39,19,19,19,19,39,39,39,39,19,39,39,39,39,19,39,19,39,19,39,19,39,19,19,19,39,19,38,38,19,38}
(1 row)

postgres=> select setseed(-1);
 setseed
---------

(1 row)

postgres=> select array(select floor(random()*40) from generate_series(1,
40));
                                              ?column?

-----------------------------------------------------------------------------------------------------

{20,0,20,20,0,20,0,0,0,0,20,20,20,20,0,0,0,0,20,0,0,0,0,20,0,20,0,20,0,20,0,20,20,20,0,20,1,1,20,1}
(1 row)

It gets somewhat better as things progress, but the start of the sequence
exhibits very clear non-randomness.

The cause seems to be GNU libc:

$ cat x.c
#include <stdio.h>
#include <stdlib.h>

main()
{
    int i;
    srandom(0x7FFFFFFF);
    for (i = 0; i < 40; i++)
        printf(i?",%d":"%d", (random()/(RAND_MAX/40)));
    puts("");
}

$ make x
cc     x.c   -o x

$ ./x
19,39,19,19,39,19,39,39,39,39,19,19,19,19,39,39,39,39,19,39,39,39,39,19,39,19,39,19,39,19,39,19,19,19,39,19,38,38,19,38

$ dpkg -l libc6 | grep libc6
ii  libc6:i386                                                  2.17-3
                        i386         Embedded GNU C Library: Shared
libraries

PostgreSQL should probably use its own pseudo-random number generator and
not depend on the system's, as there's scholar literature (e.g. Knuth's
TAOCP) indicating that many systems' default generator has poor quality. Any
replacement PRNG should preferably be cross-platform compatible, thus
providing sequence repeatability across platforms, modulo float rounding
errors. A fast and more reliable (non-crypto) PRNG such as Mersenne Twister
or WELL is not hard to implement and they tend to be fast enough for most
purposes.

On top on that, the returned value does not really have full float8
precision:

postgres=> select mod((random()*2147483648)::numeric(14,4), 1);
  mod
--------
 0.0000
(1 row)

(the latter output happens always no matter how many times it's tried).