Аддитивные генераторы
Аддитивные генераторы
Второй стандартный метод получения "более случайных" чисел от простого генератора называется аддитивным.
В соответствии с этим методом, мы инициализируем массив чисел с плавающей запятой с помощью простого генератора, например, минимального стандартного генератора случайных чисел, а затем используем два индекса в массиве для генерации последовательности случайных чисел на основе следующего алгоритма. Складываем значения, на которые указывают два индекса и записываем результат в элемент, на который указывает первый индекс (если полученная сумма будет больше 1.0, перед сохранением результата мы вычитаем из суммы значение 1.0). Возвращаем полученное значение в качестве следующего случайного числа. Перемещаем оба индекса вперед на одну позицию, при необходимости переходя от конца массива к его началу. Далее процесс повторяется снова.
Листинг 6.10. Аддитивный генератор
type
TtdAdditiveGenerator = class (TtdBasePRNG) private
FInx1 : integer;
FInx2 : integer;
FPRNG : TtdMinStandardPRNG;
FTable : array [0..54] of double;
protected
procedure agSetSeed(aValue : longint);
procedure agInitTable;
public
constructor Create(aSeed : longint);
destructor Destroy; override
function AsDouble : double; override
property Seed : longint write agSetSeed;
end;
constructor TtdAdditiveGenerator.Create(aSeed : longint);
begin
inherited Create;
FPRNG := TtdMinStandardPRNG.Create(aSeed);
agInitTable;
FInx1 := 54;
FInx2 := 23;
end;
destructor TtdAdditiveGenerator.Destroy;
begin
FPRNG.Free
inherited Destroy;
end;
procedure TtdAdditiveGenerator.agSetSeed(aValue : longint);
begin
FPRNG.Seed := aValue;
agInitTable;
end;
procedure TtdAdditiveGenerator.agInitTable;
var
i : integer;
begin
for i := 54 downto 0 do
FTable[i] := FPRNG.AsDouble;
end;
function TtdAdditiveGenerator.AsDouble : double;
begin
Result := FTable[FInx1] + FTable[FInx2];
if (Result >= 1.0) then
Result := Result - 1.0;
FTable[FInx1] := Result;
inc(FInx1);
if (FInx1 >= 55) then
FInx1 := 0;
inc(FInx2);
if (FInx2 >= 55) then
FInx2 := 0;
end;
Если внимательно изучить код, показанный в листинге 6.10, можно обратить внимание, что для формирования массива, используемого при работе аддитивного генератора, применяется минимальный стандартный генератор случайных чисел. Несмотря на то что мы не можем определить "начальное число" для аддитивного генератора (фактически по истечении некоторого времени начальное число эквивалентно всему массиву;
внутренний генератор псевдослучайных чисел вызывается только 55 раз), мы можем его установить. При установке начального значения вызывается внутренний генератор, который заполняет массив, предназначенный для инициализации аддитивного генератора.
Длина массива, 55, и значения индексов, 54 и 23, - это не просто взятые наугад значения. Было показано, что они дают хорошие последовательности случайных чисел при генерации целых значений. (В книге [11] можно найти таблицы других удачных значений длины массива и индексов.)
Самым хорошим свойством данного генератора является длина цикла. Она просто огромна (при реализации на основе значений типа longint длина цикла будет составлять 230(255- 1), или приблизительно 3 * 1025). Даже если бы вы генерировали каждую секунду триллион случайных чисел, то для того, чтобы пройти весь цикл, потребовались бы годы.