Бакнелл Джулиан М.
Шрифт:
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). Даже если бы вы генерировали каждую секунду триллион случайных чисел, то для того, чтобы пройти весь цикл, потребовались бы годы.
Тасующие генераторы
И последний тип рассматриваемых нами генераторов, позволяющих получать "более случайные" числа, принадлежит к алгоритмам тасования. Здесь мы опишем генератор, реализованный на основе одного внутреннего генератора, хотя существуют и другие генераторы, аналогичным образом использующие два внутренних генератора.
Как и для аддитивного генератора, на первом этапе создается массив случайных чисел с плавающей запятой. Количество элементов в массиве не имеет особого значения. Кнут (Knuth) предложил использовать длины порядка 100. В нашем примере будет использоваться массив из 97 элементов - простое число, близкое к 100 [11]. (Кстати, применение простого числа не обязательно, оно просто выбрано в качестве примера.) Заполним массив случайными числами, полученными с помощью минимального стандартного генератора случайных чисел. Введем новую вспомогательную переменную и установим ее значение равным следующему случайному числу в последовательности.
При необходимости генерации следующего случайного числа с помощью тасующего генератора, вспомогательная переменная используется для вычисления случайного числа из диапазона от 0 до 96. Устанавливаем значение вспомогательной переменной равным значению элемента с вычисленным индексом и заменяем элемент новым случайным числом, полученным от внутреннего генератора случайных чисел. В качестве результата тасующего генератора используется значение вспомогательной переменной.
Листинг 6.11. Тасующий генератор
type
TtdShuffleGenerator = class(TtdBasePRNG) private
FAux : double;
FPRNG : TtdMinStandardPRNG;
FTable : array [0..96] of double;
protected
procedure sgSetSeed(aValue : longint);
procedure sgInitTable;
public
constructor Create(aSeed : longint);
destructor Destroy; override;
function AsDouble : double; override;
property Seed : longint write sgSetSeed;
end;
constructor TtdShuffleGenerator.Create(aSeed : longint);
begin
inherited Create;
FPRNG := TtdMinStandardPRNG.Create(aSeed);
sgInitTable;
end;
destructor TtdShuffleGenerator.Destroy;
begin
FPRNG.Free;
inherited Destroy;
end;
function TtdShuffleGenerator.AsDouble : double;
var
Inx : integer;
begin
Inx := Trunc(FAux * 97.0);
Result := FTable[Inx];
FAux := Result;
FTable[Inx] := FPRNG.AsDouble;
end;
procedure TtdShuffleGenerator.sgSetSeed(aValue : longint);
begin
FPRNG.Seed := aValue;
sgInitTable;
end;
procedure TtdShuffleGenerator.sgInitTable;
var
i : integer;
begin
for i := 96 downto 0 do
FTable[i] := FPRNG.AsDouble;
FAux := FPRNG.AsDouble;
end;
Принимая во внимание, что приведенный генератор возвращает точно те же случайные числа, что и минимальный стандартный генератор, очень интересно обнаружить, что при проверке его в тестовой программе регулярность не проявляется.