Previous: Random Numbers, Up: Random Numbers [Contents][Index]

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’s 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

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.

Previous: Random Numbers, Up: Random Numbers [Contents][Index]