Fix broken behavior of RANDOM when given modulus that exceeds B. The
old implementation just scaled a random element (uniformly distributed
integer between 0 and B-1 inclusive) into the given range; this
strategy works fine for a modulus <= B but breaks pretty badly for
larger B.
In addition, RANDOM now generates an error if the modulus is a real
number but neither an exact positive integer nor an inexact real. The
old behavior in this case was arbitrary, not terribly useful, and
likely to be at odds with the user's expectations.
Here are some tests using the "ent" program that show the problem with
the old RANDOM implementation.
The first example is a 128MB file generated by repeatedly calling
(RANDOM (EXPT 2 64)), slicing each random number into bytes, and
writing the bytes to the file. The result is appalling:
Entropy = 7.500650 bits per byte.
Optimum compression would reduce the size
of this
134217728 byte file by 6 percent.
Chi square distribution for
134217728 samples is
515675588.87, and
randomly would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 111.9516 (127.5 = random).
Monte Carlo value for Pi is 3.
365650585 (error 7.13 percent).
Serial correlation coefficient is -0.031868 (totally uncorrelated = 0.0).
In contrast, here is the result from a file of the same length
generated using (RANDOM 256). This throws away 75% of each random
element, but shows the quality of the underlying generator:
Entropy = 7.999999 bits per byte.
Optimum compression would reduce the size
of this
134217728 byte file by 0 percent.
Chi square distribution for
134217728 samples is 235.11, and
randomly would exceed this value 75.00 percent of the times.
Arithmetic mean value of data bytes is 127.5060 (127.5 = random).
Monte Carlo value for Pi is 3.
141120183 (error 0.02 percent).
Serial correlation coefficient is -0.000131 (totally uncorrelated = 0.0).
The new design uses enough random elements to guarantee a uniform
distribution, no matter what the size of the modulus, by iteratively
adding and scaling the elements. This preserves the quality of the
underlying generator, as shown by this result:
Entropy = 7.999999 bits per byte.
Optimum compression would reduce the size
of this
134217728 byte file by 0 percent.
Chi square distribution for
134217728 samples is 263.59, and
randomly would exceed this value 50.00 percent of the times.
Arithmetic mean value of data bytes is 127.5114 (127.5 = random).
Monte Carlo value for Pi is 3.
141132700 (error 0.01 percent).
Serial correlation coefficient is -0.000044 (totally uncorrelated = 0.0).