Fix broken behavior of RANDOM when given modulus that exceeds B. The
authorChris Hanson <org/chris-hanson/cph>
Wed, 26 Nov 2003 07:00:40 +0000 (07:00 +0000)
committerChris Hanson <org/chris-hanson/cph>
Wed, 26 Nov 2003 07:00:40 +0000 (07:00 +0000)
commit6df95968d8077af63d2e55a8c5a9d389d94bbda5
tree36d87c51cb24f740de0140db7a7a756192a03091
parent21f6cfda213fc01c27fa11c2fc4792a0219aee53
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).
v7/src/runtime/random.scm