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

Линейный конгруэнтный метод

Линейный конгруэнтный метод

Следующий большой шаг в разработке генераторов случайных чисел был сделан Д. Лемером (D.H. Lehmer) в 1949 году. Предложенный им генератор носит название линейного конгруэнтного метода (linear congruential method). Выберите три числа m, a и c и начальное число Х(_0_). Для генерации последовательности случайных чисел используется следующая формула:

Х(_n+1_) = (аХ(_n_) + с) mod m

Операция взятия по модулю m (mod m) представляет собой вычисление остатка от деления числа на m, например, 24 mod 10 = 4.

При удачном выборе начальных чисел генерируемая последовательность будет содержать случайные числа. Например, стандартный генератор случайных чисел в Delphi использует значения a = 134775813 ($8088405), c = 1 и m = 2(^32^), а значение Х(_0_) выбирается самим пользователем. (Значение начального числа содержится в глобальной переменной RandSeed. Его можно задавать напрямую или использовать процедуру Randomize для вычисления его на основе показаний системных часов.)

Следует отметить, что если в двух разных точках последовательности получено одно и то же значение x, то последовательность в этих двух точках должна полностью повторяться, поскольку алгоритм детерминированный. Так как в формуле используется операция определения остатка от деления, все значения в последовательности будут меньше m, т.е. будут находиться в диапазоне от 0 до m-1. Следовательно, последовательность будет повторяться после не более чем m чисел. При неудачном выборе значения a, c и m повторение последовательности может начаться гораздо раньше. В качестве простого примера можно привести случай, когда a = 0: вся последовательность сводится к повторению значения параметра c - {c, c, c, . . .}

Каким образом можно выбрать удачные значения для a, c и m? В литературе содержится немало размышлений, описаний и доказательств. Как правило, значение параметра m выбирается как можно больше, чтобы цикл повторяемости был также как можно большим. Нужно выбирать его, как минимум, равным размеру слова операционной системы (другими словами, для 32-разрядных операционных систем m выбирается равным 31 или 32 бита). Значение параметра а выбирается таким образом, чтобы оно было взаимно простым со значением числа m (два числа являются взаимно простыми, если их наибольший общий делитель равен 1). Значение c, как правило, берется равным 0 или 1, несмотря на то, что общее правило гласит, что должно выбираться ненулевое значение, взаимно простое со значением параметра m.

В случае если значение с равно 0, генератор называется мультипликативным линейным конгруэнтным генератором случайных чисел (multiplicative linear congruential generator). Чтобы гарантировать, что цикл повторения последовательности максимален, необходимо в качестве значения параметра m выбирать простое число. Самым известным генератором подобного рода является так называемый минимальный стандартный генератор случайных чисел (minimal standard random number generator), предложенный Стивеном Парком (Stephen Park) и Кейтом Миллером (Keith Miller) в 1988 году. Для него а = 16807, а m = 2147483647 (или 2(^31^) - 1). После разработки этого генератора было проведено большое количество статистических тестов, и генератор прошел большинство из них (несмотря на то что предложенный генератор обладает определенными нежелательными свойствами, которые мы рассмотрим чуть ниже).

Мультипликативные линейные конгруэнтные генераторы случайных чисел имеют одну аномалию: они никогда не дают числа 0. (Это объясняется тем, что, во-первых, m представляет собой простое число, во-вторых, a mod m не равно нулю, и, в-третьих, если начальное число не равно нулю, Х(_0_) mod m тоже не равно нулю.) Следовательно, если генераторы никогда не дают числа 0, их нельзя назвать случайными. На практике невозможность генерации нуля, как правило, игнорируется, - в конце концов, в 32-разрядной операционной системе это всего лишь отсутствие всего одного числа из примерно 2 миллиардов.

При реализации минимального стандартного генератора случайных чисел (как, в общем-то, и любого другого) особое внимание необходимо уделить исключению возможности возникновения переполнения, поскольку значение текущего начального числа, умноженное на а, может легко превысить максимально допустимое значение для 32-битного целого числа. Если не позаботиться об исключении переполнения, возможно возникновение ошибок, которые негативно скажутся на достаточно хорошем генераторе случайных чисел. Для обработки случаев переполнения используется метод Шрейга (Schrage) (его описание в этой книге не приводится, но его можно найти в статье Парка и Миллера [16]).

Для сравнения и тестирования различных генераторов случайных чисел будет создана иерархия классов, базовый класс которой будет содержать виртуальный метод, инкапсулирующий основные функциональные возможности генератора, в частности, генерация случайного числа с плавающей запятой в диапазоне от 0 до 1 (мы будем пользоваться переменными типа double). Этот виртуальный метод будет перекрываться в дочерних классах, что позволит генерировать случайное число в соответствии с алгоритмами дочерних классов. В базовом классе метод будет применяться для создания других типов случайных чисел, например, случайных чисел целого типа не больше определенного значения или случайного числа из определенного диапазона.

Наличие иерархии классов генераторов случайных чисел дает еще одно преимущество. Поскольку данные для генератора случайных чисел содержатся исключительно внутри самого объекта, в одном приложении можно будет использовать несколько независимых генераторов. Стандартная функция Random имеет одно и только одно начальное значение, которое будет использоваться для всех вызовов функции в приложении. В ситуации, когда несколько различных процедур прибегают к услугам функции Random, очень сложно получить воспроизводимые результаты, поскольку отдельные вызовы будут влиять на получаемые случайные значения.

Листинг 6.2. Базовый класс генератора случайных чисел

type

TtdBasePRNG = class private

FName : TtdNameString;

protected procedure bError(aErrorCode : integer;

const aMethodName : TtdNameString);

public

function AsDouble : double; virtual;

abstract;

{вернуть случайное число из диапазона от 0 включительно до 1 исключительно}

function AsLimitedDouble(aLower, aUpper : double): double;

{-вернуть случайное число из диапазона от aLower включительно до aUpper исключительно}

function AsInteger(aUpper : integer): integer;

{-вернуть случайное число из диапазона от 0 включительно до aUpper исключительно}

property Name : TtdNameString read FName write FName;

end;

function TtdBasePRNG.AsLimitedDouble(aLower, aUpper : double): double;

begin

if (aLower < 0.0) or (aUpper < 0.0) or (aLower >= aUpper) then

bError(tdeRandRangeError, 'AsLimitedDouble');

Result := (AsDouble * (aUpper - aLower)) + aLower;

end;

function TtdBasePRNG.AsInteger(aUpper : integer): integer;

begin

if (aUpper <= 0) then

bError(tdeRandRangeError, 'AsInteger');

Result := Trunc(AsDouble * aUpper);

end;

procedure TtdBasePRNG.bError(aErrorCode : integer;

const aMethodName : TtdNameString);

begin

raise EtdRandGenException.Create(

FmtLoadStr(aErrorCode,

[UnitName, ClassName, aMethodName, Name]));

end;

В листинге 6.2 приведен код базового класса генератора случайных чисел. В нем определен виртуальный метод AsDouble, который возвращает случайное число X в диапазоне 0< х< 1. Кроме того, в классе объявлены два простых метода, один из которых возвращает случайное число с плавающей запятой из заданного диапазона значений, а второй - из диапазона значений от 0 до некоторой заданной верхней границы (аналогично тому, как функция Random (Limit) использует целое значение Limit). Теперь, когда базовый класс определен, для реализации алгоритма Парка и Миллера можно объявить дочерний класс.

Листинг 6.3. Минимальный стандартный генератор псевдослучайных чисел

type

TtdMinStandardPRNG = class(TtdBasePRNG) private

FSeed : longint;

protected

procedure msSetSeed(aValue : longint);

public

constructor Create(aSeed : longint);

function AsDouble : double; override;

property Seed : longint read FSeed write msSetSeed;

end;

constructor TtdMinStandardPRNG.Create(aSeed : longint);

begin

inherited Create;

Seed := aSeed;

end;

function TtdMinStandardPRNG.AsDouble : double;

const

a = 16807;

m = 2147483647;

q = 127773; {равно m diva}

r = 2836; {равно m mod a}

OneOverM : double = 1.0 / 2147483647.0;

var

k : longint;

begin

k := FSeed div q;

FSeed := (a * (FSeed - (k * q))) - (k * r);

if (FSeed <= 0) then

inc( FSeed, m);

Result := FSeed * OneOverM;

end;

function GetTimeAsLong : longint;

{$IFDEF Delphi1}

assembler;

asm

mov ah, $2С

call DOS3Call

mov ax, cx end;

{$ENDIF}

{$IFDEF Delph2Plus}

begin

Result := longint(GetTickCount);

end;

{$ENDIF}

{$IFDEF KylixlPlus}

var

T : TTime_t;

begin

_time(@T);

Result := longint(T);

end;

{$ENDIF}

procedure TtdMinStandardPRNG.msSetSeed(aValue : longint);

const

m = 2147483647;

begin

if (aValue > 0) then

FSeed := aValue

else

FSeed := GetTimeAsLong;

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

if (FSeed >=m-1) then

FSeed := FSeed - (m - 1) + 1;

end;

Как несложно заметить в коде метода AsDouble, метод Шрейга выглядит гораздо сложнее, нежели простая формула X(_n+1_) = aX(_n_) mod m со значениями а = 16807 и m = 2(^31^) - 1. Тем не менее, используя достаточно сложные математические выкладки, можно доказать его равенство приведенной формуле.

Кроме того, как уже упоминалось, в генераторе случайных чисел подобного типа использование нуля в качестве начального числа нежелательно, поскольку тогда бы все генерируемые значения были бы нулевыми. Поэтому метод msSetSeed использует значение 0 в качестве флага при необходимости установки начального числа по значению системных часов. К сожалению, для выполнения этой операции в 16- и 32-разрядных системах Windows используется разный код.

Создадим класс случайных чисел, который будет использовать системный генератор случайных чисел - функцию Random. В листинге 6.4 показан код метода AsDouble для такого класса.

Листинг 6.4. Использование в классе системной функции Random

function TtdSystemPRNG.AsDouble : double;

var

OldSeed : longint;

begin

OldSeed := System.RandSeed;

System.RandSeed := Seed;

Result := System.Random;

Seed := System.RandSeed;

System.RandSeed := OldSeed;

end;

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

Оглавление книги