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 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.