Random Number Generator
-----------------------

Calc's random number generator uses several methods to ensure that the
numbers it produces are highly random.  Knuth's *Art of Computer
Programming*, Volume II, contains a thorough description of the theory
of random number generators and their measurement and
characterization.

If `RandSeed' has no stored value, Calc calls Emacs' built-in `random'
function to get a stream of random numbers, which it then treats in
various ways to avoid problems inherent in the simple random number
generators that many systems use to implement `random'.

When Calc's random number generator is first invoked, it "seeds" the
low-level random sequence using the time of day, so that the random
number sequence will be different every time you use Calc.

Since Emacs Lisp doesn't specify the range of values that will be
returned by its `random' function, Calc exercises the function several
times to estimate the range.  When Calc subsequently uses the `random'
function, it takes only 10 bits of the result near the
most-significant end.  (It avoids at least the bottom four bits,
preferably more, and also tries to avoid the top two bits.)  This
strategy works well with the linear congruential generators that are
typically used to implement `random'.

If `RandSeed' contains an integer, Calc uses this integer to seed an
"additive congruential" method (Knuth's algorithm 3.2.2A, computing
`X_n-55 - X_n-24').  This method expands the seed value into a large
table which is maintained internally; the variable `RandSeed' is
changed from, e.g., 42 to the vector `[42]' to indicate that the seed
has been absorbed into this table.  When `RandSeed' contains a vector,
`k r' and related commands continue to use the same internal table as
last time.  There is no way to extract the complete state of the
random number generator so that you can restart it from any point; you
can only restart it from the same initial seed value.  A simple way to
restart from the same seed is to type `s r RandSeed' to get the seed
vector, `v u' to unpack it back into a number, then `s t RandSeed' to
reseed the generator with that number.

Calc uses a "shuffling" method as described in algorithm 3.2.2B of
Knuth.  It fills a table with 13 random 10-bit numbers.  Then, to
generate a new random number, it uses the previous number to index
into the table, picks the value it finds there as the new random
number, then replaces that table entry with a new value obtained from
a call to the base random number generator (either the additive
congruential generator or the `random' function supplied by the
system).  If there are any flaws in the base generator, shuffling will
tend to even them out.  But if the system provides an excellent
`random' function, shuffling will not damage its randomness.

To create a random integer of a certain number of digits, Calc builds
the integer three decimal digits at a time.  For each group of three
digits, Calc calls its 10-bit shuffling random number generator (which
returns a value from 0 to 1023); if the random value is 1000 or more,
Calc throws it out and tries again until it gets a suitable value.

To create a random floating-point number with precision P, Calc simply
creates a random P-digit integer and multiplies by `10^-p'.  The
resulting random numbers should be very clean, but note that
relatively small numbers will have few significant random digits.  In
other words, with a precision of 12, you will occasionally get numbers
on the order of `10^-9' or `10^-10', but those numbers will only have
two or three random digits since they correspond to small integers
times `10^-12'.

To create a random integer in the interval `[0 .. M)', Calc counts the
digits in M, creates a random integer with three additional digits,
then reduces modulo M.  Unless M is a power of ten the resulting
values will be very slightly biased toward the lower numbers, but this
bias will be less than 0.1%.  (For example, if M is 42, Calc will
reduce a random integer less than 100000 modulo 42 to get a result
less than 42.  It is easy to show that the numbers 40 and 41 will be
only 2380/2381 as likely to result from this modulo operation as
numbers 39 and below.)  If M is a power of ten, however, the numbers
should be completely unbiased.

The Gaussian random numbers generated by `random(0.0)' use the "polar"
method described in Knuth section 3.4.1C.  This method generates a
pair of Gaussian random numbers at a time, so only every other call to
`random(0.0)' will require significant calculations.