[Sbcl-devel] Random floats

[<m_m...@ya...>]

Hello,

I attach a patch that improves the quality of random floating point
number generation by ensuring that all the bits of the mantissa are
random. Currently, the lower bits of small numbers are biased.  A
description of the issue can be found on page 4 in this article:
<www.mathworks.com/moler/random.pdf>. My solution is similar to that of
[1], except that I do almost everything with bitwise operators.

One way to see the issue with the bias in the lower bits is to run the
mintest-d function included in the attached file testfrng.lisp. It
displays the bit pattern (sign, exponent, mantissa) of successively
smaller random numbers. The smaller the numbers, the more zeros you
will observe in the lower bits. If you run again the test with the
patch applied, you will see that all bits become random. If you run
(random 1.0d0) often enough with the patch applied, all possible
double-floats in [0,1) will eventually be generated, including the
subnormal ones.

I've tried to make sure that the speed of random number generation does
not degrade too much. On my computer, the FP RNGs become slower by
slightly less than 10%.

The testfrng.lisp file contains additional routines for playing with
this and testing that everything is ok by using the program ent [2].

Please let me know if you have any comments or questions.

Regards,
       Mario

[1] <http://www.home.hs-karlsruhe.de/~moth0001/forschung/Uniform%20and%20
Exponential%20Random%20Floating%20OR2007.pdf>

[2] <http://www.fourmilab.ch/random/>