The Common Lisp facility for generating pseudo-random numbers has been carefully defined to make its use reasonably portable. While two implementations may produce different series of pseudo-random numbers, the distribution of values should be relatively independent of such machine-dependent aspects as word size.
(random n) accepts a positive number n and returns a number of the same kind between zero (inclusive) and n (exclusive). The number n may be an integer or a floating-point number. An approximately uniform choice distribution is used. If n is an integer, each of the possible results occurs with (approximate) probability 1/n. (The qualifier “approximate” is used because of implementation considerations; in practice, the deviation from uniformity should be quite small.)
The argument state must be an object of type random-state; it defaults to the value of the variable *random-state*. This object is used to maintain the state of the pseudo-random-number generator and is altered as a side effect of the random operation. _______________________________________________________
Implementation note: In general, even if random of zero arguments were defined as in MacLisp, it is not adequate to define (random n) for integral n to be simply (mod (random) n); this fails to be uniformly distributed if n is larger than the largest number produced by random, or even if n merely approaches this number. This is another reason for omitting random of zero arguments in Common Lisp. Assuming that the underlying mechanism produces “random bits” (possibly in chunks such as fixnums), the best approach is to produce enough random bits to construct an integer k some number d of bits larger than (integer-length n) (see integer-length), and then compute (mod k n). The quantity d should be at least 7, and preferably 10 or more.
To produce random floating-point numbers in the half-open range [A,B), accepted practice (as determined by a look through the Collected Algorithms from the ACM, particularly algorithms 133, 266, 294, and 370) is to compute X ⋅ (B −A) + A, where X is a floating-point number uniformly distributed over [0.0,1.0) and computed by calculating a random integer N in the range [0,M) (typically by a multiplicative-congruential or linear-congruential method mod M) and then setting X = N∕M. See also [27]. If one takes M = 2f, where f is the length of the significand of a floating-point number (and it is in fact common to choose M to be a power of 2), then this method is equivalent to the following assembly-language-level procedure. Assume the representation has no hidden bit. Take a floating-point 0.5, and clobber its entire significand with random bits. Normalize the result if necessary.
For example, on the DEC PDP-10, assume that accumulator T is completely random (all 36 bits are random). Then the code sequence
will produce in T a random floating-point number uniformly distributed over [0.0,1.0). (Instead of the LSH instruction, one could do
but if the 36 random bits came from a congruential random-number generator, the high-order bits tend to be “more random” than the low-order ones, and so the LSH would be better for uniform distribution. Ideally all the bits would be the result of high-quality randomness.)
With a hidden-bit representation, normalization is not a problem, but dealing with the hidden bit is. The method can be adapted as follows. Take a floating-point 1.0 and clobber the explicit significand bits with random bits; this produces a random floating-point number in the range [1.0,2.0). Then simply subtract 1.0. In effect, we let the hidden bit creep in and then subtract it away again.
For example, on the DEC VAX, assume that register T is completely random (but a little less random than on the PDP-10, as it has only 32 random bits). Then the code sequence
will produce in T a random floating-point number uniformly distributed over [0.0,1.0). Again, if the low-order bits are not random enough, then the instruction
should be performed first.
Implementors may wish to consult reference [41] for a discussion of some efficient methods of generating pseudo-random numbers.
This variable holds a data structure, an object of type random-state, that encodes the internal state of the random-number generator that random uses by default. The nature of this data structure is implementation-dependent. It may be printed out and successfully read back in, but may or may not function correctly as a random-number state object in another implementation. A call to random will perform a side effect on this data structure. Lambda-binding this variable to a different random-number state object will correctly save and restore the old state object.
This function returns a new object of type random-state, suitable for use as the value of the variable *random-state*. If state is nil or omitted, make-random-state returns a copy of the current random-number state object (the value of the variable *random-state*). If state is a state object, a copy of that state object is returned. If state is t, then a new state object is returned that has been “randomly” initialized by some means (such as by a time-of-day clock). ____________________________________________________________________
Rationale: Common Lisp purposely provides no way to initialize a random-state object from a user-specified “seed.” The reason for this is that the number of bits of state information in a random-state object may vary widely from one implementation to another, and there is no simple way to guarantee that any user-specified seed value will be “random enough.” Instead, the initialization of random-state objects is left to the implementor in the case where the argument t is given to make-random-state.
To handle the common situation of executing the same program many times in a reproducible manner, where that program uses random, the following procedure may be used:
It is for the sake of this procedure for reproducible execution that implementations are required to provide a read/print syntax for objects of type random-state.
It is also possible to make copies of a random-state object directly without going through the print/read process, simply by using the make-random-state function to copy the object; this allows the same sequence of random numbers to be generated many times within a single program.
Implementation note: A recommended way to implement the type random-state is effectively to use the machinery for defstruct. The usual structure syntax may then be used for printing random-state objects; one might look something like
where the components are of course completely implementation-dependent.
random-state-p is true if its argument is a random-state object, and otherwise is false.