Re: doc: Mention rand and srand limitations

[Bruno Haible]

Jeffrey Walton wrote:
> > The attached program tests the MT-safety. Results: OK on all platforms, 
> > except
> > ...
> 
> If rand() and friends do not need to be MT-safe, then does it even need a 
> test?

I wrote the test (but did not commit it into gnulib) because rand() is MT-safe
on GNU. If I made the incorrect assumption that it then would be MT-safe on all
platforms, other people may make the same assumption. Therefore it's worth
documenting the issue: it's a portability issue.

> I think the two tests of interest are:
> 
> (1) srand() produces a repeatable stream

I posted a test case for the Cygwin people here:
  <https://sourceware.org/pipermail/cygwin/2023-November/254735.html>
Since multithreaded use of rand() is better avoided (and random() used
instead), I'm not adding a workaround to this Cygwin bug to Gnulib.

> (2) rand() and friends produce a stream that is uniformly distributed

It is sufficiently well-known that rand() has a poor quality. ISO C 23
has an explicit reminder:
  "Recommended practice
   There are no guarantees as to the quality of the random sequence
   produced and some implementations are known to produce sequences
   with distressingly non-random low-order bits. Applications with
   particular requirements should use a generator that is known to be
   sufficient for their needs."

What I remember from earlier reading (decades ago) is that the two or three
lowest bits of the result of rand() are not equidistributed and therefore
should better be discarded; which is what I'm doing in the Gnulib code.

> For (2), compressibility is a poor man's randomness test.

I don't think good compressibility is equivalent to poor quality as a
random sequence. Good compressibility certainly implies poor quality.
But I conjecture that the opposite inference is not true: That you can
have poor quality pseudo-random generators that don't compress well.
Poor quality of pseudo-random numbers can mean
  - a small cycle length, or
  - not well equi-distributed.
Knuth [1] gives examples of pseudo-random number generators which look
good when you look at their distribution in 2 dimensions, but look bad
when considered in 3 dimensions, IIRC.

> You could also use Maurer's Universal Statistical Test for Random Bit
> Generators from Journal of Cryptology, 1992. Maurer's test is a test
> for physical generators. But a quality pseudo random number generator
> will follow a uniform distribution, and it should be indistinguishable
> from a physical generator. I know they are indistinguishable for a
> cryptographically secure pseudo random number generator.

Such a test would be useful for someone who needs good-quality pseudo-
random numbers _and_ uses an unknown implementation. But
  - rand() is known to be poor-quality,
  - *rand48 has a fixed implementation [2], therefore it's pointless
    to want to test its quality.

Bruno

[1] Donald Knuth: The Art Of Computer Programming, vol II:
    Seminumerical Algorithms
[2] https://pubs.opengroup.org/onlinepubs/9699919799/functions/drand48.html