Фундаментальные алгоритмы и структуры данных в Delphi

Бакнелл Джулиан М.

end;

constructor TtdCombinedPRNG.Create(aSeed1, aSeed2 begin

inherited Create;

Seed1 := aSeed1;

Seed2 := aSeed2;

end;

longint);

function TtdCombinedPRNG.AsDouble : double;

const

al = 40014;

m1 = 2147483563;

ql = 53668;

{равно m1 div al}

rl = 12211;

{равно m1 mod al}

a2 = 40692;

m2 = 2147483399;

q2 = 52774;

{равно m2 div a2}

r2 = 3791;

{равно m2 mod a2}

OneOverMl : double = 1.0 / 2147483563.0;

var k : longint;

Z : longint;

begin

{получить

случайное число с помощью первого генератора}

k := FSeed1 div ql;

FSeed1 := (al * (FSeed1 - (k * ql))) - (k * rl);

if (FSeed1 <= 0) then

inc(FSeed1, m1);

{получить случайное число с помощью второго генератора}

k := FSeed2 divq2;

FSeed2 := (a2 * (FSeed2 - (k * q2))) - (k * r2);

if (FSeed2 <= 0) then

inc(FSeed2, m2);

{объединить два случайных числа}

Z := FSeed1 - FSeed2;

if (Z <= 0) then

Z := Z + m1 - 1;

Result := Z * OneOverMl;

end;

procedure TtdCombinedPRNG.cpSetSeed1(aValue : longint);

const

m1 = 2147483563;

begin

if (aValue > 0) then

FSeed1 := aValue

else

FSeed1 := GetTimeAsLong;

{убедиться, что случайное число находится в диапазоне от 1 до m-1 включительно}

if (FSeed1 > - m1-1) then

FSeed1 := FSeed1 - (m1-1) + 1;

end;

procedure TtdCombinedPRNG.cpSetSeed2(aValue : longint);

const

m2 = 2147483399;

begin

if (aValue > 0) then

FSeed2 := aValue else

FSeed2 := GetTimeAsLong;

{убедиться, что случайное число находится в диапазоне от 1 до m-1 включительно}

if (FSeed2 >=m2-1) then

FSeed2 := FSeed2 - (m2 - 1) + 1;

end;

Как видите, код метода AsDouble в листинге 6.9 содержит два мультипликативных линейных конгруэнтных генератора: первый с параметрами {а, m} = {40014,2147483563}

и второй с параметрами {а, m} = {40692, 2147483399}.

Циклы обоих генераторов отличаются, но, тем не менее, близки к 2(^31^). Для преобразования промежуточного значения типа longint в значение типа double используется генератор с более длинным циклом.

Приведенный в листинге 6.9 генератор исключает двухмерную регулярность простого мультипликативного линейного конгруэнтного генератора, в чем можно убедиться с помощью программы тестирования. Можно показать, что длина цикла полученного комбинированного генератора составляет примерно 2 * 10(^18^). (Для сравнения, длина цикла стандартного генератора Delphi примерно равна 4 * 10(^9^).) Последовательность, вычисляемая с помощью комбинированного генератора полностью, определяется двумя начальными числами - по одному для каждого внутреннего генератора, в то время как для простого мультипликативного генератора было достаточно одного числа.

Аддитивные генераторы

Второй стандартный метод получения "более случайных" чисел от простого генератора называется аддитивным.

В соответствии с этим методом, мы инициализируем массив

чисел с плавающей запятой с помощью простого генератора, например, минимального стандартного генератора случайных чисел, а затем используем два индекса в массиве для генерации последовательности случайных чисел на основе следующего алгоритма. Складываем значения, на которые указывают два индекса и записываем результат в элемент, на который указывает первый индекс (если полученная сумма будет больше 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 раз), мы можем его установить. При установке начального значения вызывается внутренний генератор, который заполняет массив, предназначенный для инициализации аддитивного генератора.