12.9 Случайные числа

Функциональность Common Lisp’а для генерации псевдослучайных чисел была аккуратно проработана, чтобы быть переносимой. Тогда как две реализации могут создавать различные ряды псевдослучайных чисел, распределение значений должно быть независимо от таких характеристик компьютера как размер слова.

[Функция] random number &optional state

(random n) принимает положительное число n и возвращает число такого же типа между нулём (включительно) и n (невключительно). Число n может быть целым или с плавающей точкой. При этом используется приблизительно равномерное распределения. FIXME Если n целое число, каждый из возможных результатов встречается с (примерной) вероятностью 1/n. (Слово «примерно» используется из-за различий реализаций. На практике отклонение от однородности должно быть весьма мало.)

Аргумент state должен быть объектом типа random-state. По-умолчанию он равен значению переменной *random-state*. Объект используется для сохранения состояния генератора псевдослучайных чисел и изменяется как побочное действие от операции random. ________________________________

Заметка для реализации: 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 ⋅ (BA) + 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 = NM. 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

LSH T,-9                 ;Clear high 9 bits; low 27 are random
FSC T,128.               ;Install exponent and normalize

will produce in T a random floating-point number uniformly distributed over [0.0,1.0). (Instead of the LSH instruction, one could do

TLZ T,777000             ;That’s 777000 octal

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

INSV #̂X81,#7,#9,T     ;Install correct sign bit and exponent
SUBF #̂F1.0,T          ;Subtract 1.0

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

ROTL #7,T

should be performed first.

Implementors may wish to consult reference [41] for a discussion of some efficient methods of generating pseudo-random numbers.

__________________________________________________________________________

[Переменная] *random-state*

Данная переменная содержит объект типа random-state, который хранит состояние для генератора случайных чисел, которое по-умолчанию используется функцией random. Природа этой структуры данных зависит от реализации. Она может быть выведена на печать и прочитана обратно, но не обязательно это может быть сделано между реализациями. Вызов random изменяет этот объект. Связывание этой переменной с другим значением будет корректно сохраняться и восстанавливаться.


[Функция] make-random-state &optional state

Данная функция возвращает новый объект типа random-state, подходящий для использования в качестве значения переменной *random-state*. Если state не указано или равно nil, тогда make-random-state возвращает копию текущего объекта состояния генератора псевдослучайных чисел (значение переменной *random-state*). Если state является объектом состояния, то возвращается копия данного объекта. Если state равен t, тогда новый возвращается новый объект состояния, который в некотором смысле «случайно» инициализирован (текущим временем например). _______________________________________________________________

Обоснование: 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:

  1. Evaluate (make-random-state t) to create a random-state object.
  2. Write that object to a file, using print, for later use.
  3. Whenever the program is to be run, first use read to create a copy of the random-state object from the printed representation in the file. Then use the random-state object newly created by the read operation to initialize the random-number generator for the program.

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.

__________________________________________________________________________

Заметка для реализации: 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

#S(RANDOM-STATE DATA #(14 49 98436589 786345 8734658324 ...))

where the components are of course completely implementation-dependent.

___________________________________________________________________________________________________________

[Функция] random-state-p object

random-state-p истинен, если аргумент является объектом состояния генератора случайных чисел, иначе — ложен.

(random-state-p x)  (typep x ’random-state)