Справочник Ada 2012

A.5.2 Генерация случайных чисел

Средства для генерации псевдослучайных чисел с плавающей точкой предоставлены в пакете Numerics.Float_Random; аналогичные средства для генерации псевдослучайных целых чисел и псевдослучайных значений типов перечисления предоставлены в обобщенном пакете Numerics.Discrete_Random. Для краткости псевдослучайные значения любого из этих типов называются случайными числами.

Некоторые из предоставляемых средств являются базовыми для всех применений случайных чисел. Они включают ограниченный частный тип, каждый объект которого служит генератором последовательности (возможно, различных) случайных чисел; функция получения «следующего» случайного числа из заданной последовательности случайных чисел (то есть из ее генератора); и подпрограммы для инициализации или повторной инициализации заданного генератора до состояния, зависящего от времени, или состояния, обозначаемого целым числом.

Другие средства предоставляются специально для сложных применений. Они включают подпрограммы для сохранения и восстановления состояния заданного генератора; частный тип, объекты которого могут использоваться для хранения сохраненного состояния генератора; и подпрограммы получения строкового представления заданного состояния генератора или, задав такое строковое представление, соответствующего состояния.

Статическая семантика

Библиотечный пакет Numerics.Float_Random имеет следующее объявление:

package Ada.Numerics.Float_Random is

-- Основные средства

type Generator is limited private;

subtype Uniformly_Distributed is Float range 0.0 .. 1.0;
function Random (Gen : Generator) return Uniformly_Distributed;

procedure Reset (Gen : in Generator;
Initiator : in Integer);
procedure Reset (Gen : in Generator);

-- Расширенные средства

type State is private;

procedure Save (Gen : in Generator;
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State);

Max_Image_Width : constant := определяемое реализацией целое значение;

function Image (Of_State : State) return String;
function Value (Coded_State : String) return State;

private
... -- не определено языком
end Ada.Numerics.Float_Random;

Тип Generator требует финализации (см. 7.6).

Обобщенный библиотечный пакет Numerics.Discrete_Random имеет следующее объявление:

generic
type Result_Subtype is (<>);
package Ada.Numerics.Discrete_Random is

-- Основные средства

type Generator is limited private;

function Random (Gen : Generator) return Result_Subtype;

procedure Reset (Gen : in Generator;
Initiator : in Integer);
procedure Reset (Gen : in Generator);

-- Расширенные средства

type State is private;

procedure Save (Gen : in Generator;
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State);

Max_Image_Width : constant := определяемое реализацией целое значение;

function Image (Of_State : State) return String;
function Value (Coded_State : String) return State;

private
... -- не определено языком
end Ada.Numerics.Discrete_Random;

Тип Generator требует финализации (см. 7.6) в каждой инстанциации Numerics.Discrete_Random.

Объект ограниченного частного типа Generator связан с последовательностью случайных чисел. Каждый генератор имеет скрытое (внутреннее) состояние, которое операции с генераторами используют для определения позиции в связанной последовательности. Все генераторы неявно инициализируются до неопределенного состояния, которое не изменяется от одного выполнения программы к другому; они также могут быть явно инициализированы или повторно инициализированы до состояния, зависящего от времени, до ранее сохраненного состояния или до состояния, однозначно обозначаемого целым значением.

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

Операции над генераторами влияют на состояние и, следовательно, на будущие значения связанной последовательности. Семантика операций над генераторами и состояниями определена ниже.

function Random (Gen : Generator) return Uniformly_Distributed;
function Random (Gen : Generator) return Result_Subtype;

Получает «следующее» случайное число из заданного генератора, относительно его текущего состояния, в соответствии с определённым реализацией алгоритмом. Результат функции в Numerics.Float_Random возвращается как значение подтипа Uniformly_Distributed, который является подтипом предопределенного типа Float с диапазоном 0.0 .. 1.0. Результат функции в инстанциации Numerics.Discrete_Random возвращается как значение обобщенного формального подтипа Result_Subtype.

procedure Reset (Gen : in Generator;
Initiator : in Integer);
procedure Reset (Gen : in Generator);

Устанавливает состояние указанного генератора в состояние, которое является неопределённой функцией значения параметра Initiator (или в состояние, зависящее от времени, если указан только параметр генератора). Последняя форма процедуры известна как процедура Reset, зависящая от времени.

procedure Save (Gen : in Generator;
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State);

Save получает текущее состояние генератора. Reset задаёт генератору указанное состояние. Генератор, который сброшен в состояние, полученное ранее вызовом Save, восстанавливается в состояние, которое он имел во время вызова Save.

function Image (Of_State : State) return String;
function Value (Coded_State : String) return State;

Image предоставляет представление состояния, закодированного (определяемым реализацией способом) как строка, длина которой ограничена значением Max_Image_Width. Value является обратной функцией Image: Value(Image(S)) = S для каждого состояния S, которое может быть получено от генератора путем вызова Save.

Динамическая семантика

Инициализация Numerics.Discrete_Random подтипом с нулевым диапазоном вызывает исключение Constraint_Error.

Этот абзац был удалён.

Ограниченные (временные) ошибки

Вызов Value со строкой, которая не является изображением состояния любого генератора, является ограниченной ошибкой. Если ошибка обнаружена, то генерируется исключение Constraint_Error или Program_Error. В противном случае вызов Reset с полученным состоянием создаст генератор, такой, что вызовы Random с этим генератором будут производить последовательность значений соответствующего подтипа, но которые могут не иметь случайного характера. То есть, последовательность значений может не удовлетворять требованиям реализации данного подраздела.

Требования к реализации

Достаточно длинная последовательность случайных чисел, полученная последовательными вызовами Random, приблизительно равномерно распределена в диапазоне подтипа результата.

Функция Random в инстанциации Numerics.Discrete_Random гарантированно вернёт каждое значение в своём подтипе результата за конечное число вызовов, при условии, что количество таких значений не превышает 2 ¹⁵.

Другие требования к производительности генератора случайных чисел, которые применяются только в реализациях, соответствующих приложению Numerics, а затем только в «строгом» режиме, определённом там (см. G.2), приведены в G.2.5.

Требования к документации

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

Реализация также должна задокументировать минимальный интервал времени между вызовами процедуры Reset, зависящей от времени, гарантирующий инициирование различных последовательностей, а также характер строк, которые Value будет принимать без генерации Constraint_Error.

Рекомендации по реализации

Любой хранилище, связанный с объектом типа Generator, должен быть высвобожден при выходе из области видимости объекта.

Если период генератора достаточно велик по отношению к количеству различных начальных значений, то каждое возможное значение Initiator, переданное в Reset, должно инициировать последовательность случайных чисел, которая практически не перекрывает последовательность, инициированную любым другим значением. Если это невозможно, то отображение между начальными значениями и состояниями генератора должно быть быстро изменяющейся функцией от начального значения.

ПРИМЕЧАНИЯ

19 Если две или более задачи используют один и тот же генератор, то задачи должны синхронизировать свой доступ к генератору, как и для любой общей переменной (см. 9.10).

20 В рамках данной реализации повторяющуюся последовательность случайных чисел можно получить, опираясь на неявную инициализацию генераторов или явно инициализируя генератор с повторяющимся начальным значением. Разные последовательности случайных чисел можно получить от данного генератора в разных запусках программы, явно инициализируя генератор в зависимости от времени.

21 Данная реализация функции Random в Numerics.Float_Random может или не может генерировать значения 0.0 или 1.0. При разработке переносимых приложений следует исходить из предположения, что эти значения или значения, достаточно близкие к ним для неразличимого поведения, могут встречаться. Если требуется последовательность случайных целых чисел из некоторого фиксированного диапазона, приложение должно использовать функцию Random в соответствующей инстанциации Numerics.Discrete_Random, а не преобразовывать результат функции Random в Numerics.Float_Random. Однако некоторые приложения со специфическими требованиями, например, для последовательности случайных целых чисел, каждый из которых выбирается из разных диапазонов, могут посчитать более удобным преобразование результата функции Random с плавающей точкой. Для M ≥ 1 выражение

Integer(Float(M) * Random(G)) mod M

преобразует результат Random(G) в целое число, равномерно распределённое в диапазоне 0 .. M–1; оно верно, даже если Random возвращает 0.0 или 1.0. Каждое значение из результата диапазона возможно, при условии, что M не слишком велико. Экспоненциально распределённые (с плавающей точкой) случайные числа со средним значением и стандартным отклонением 1.0 можно получить с помощью преобразования

-Log(Random(G) + Float'Model_Small)

где Log берется из Numerics.Elementary_Functions (см. A.5.1); в этом выражении, добавление Float'Model_Small предотвращает исключение, которое было бы вызвано, если бы Log получил значение ноль, не влияя на результат (в большинстве реализаций), когда Random возвращает ненулевое значение.

Примеры

Пример программы, моделирующей игру в кости:

с Ada.Numerics.Discrete_Random;
процедура Dice_Game is
подтип Die is Integer диапазон 1 .. 6;
подтип Dice is Integer диапазон 2*Die'First .. 2*Die'Last;
пакет Random_Die is new Ada.Numerics.Discrete_Random (Die);
use Random_Die;
G : Generator;
D : Dice;
begin
Reset (G); -- Запустить генератор в уникальном состоянии в каждом запуске
цикл
-- Бросить пару костей; суммировать и обработать результаты
D := Random(G) + Random(G);
...
конец цикла;
конец Dice_Game;

Пример программы, моделирующей подбрасывание монеты:

с Ada.Numerics.Discrete_Random;
процедура Flip_A_Coin is
тип Coin is (Heads, Tails);
пакет Random_Coin is new Ada.Numerics.Discrete_Random (Coin);
use Random_Coin;
G : Generator;
begin
Reset (G); -- Запустить генератор в уникальном состоянии в каждом запуске
цикл
-- Подбросить монету и обработать результат
случай Random(G) is
когда Heads =>
...
когда Tails =>
...
конец случая;
...
конец цикла;
конец Flip_A_Coin;

Пример параллельной симуляции физической системы с отдельным генератором вероятностей событий в каждой задаче:

с Ada.Numerics.Float_Random;
процедура Parallel_Simulation is
use Ada.Numerics.Float_Random;
задача тип Worker is
вход Initialize_Generator (Initiator : in Integer);
...
конец Worker;
W : массив (1 .. 10) of Worker;
задача тело Worker is
G : Generator;
Probability_Of_Event : Uniformly_Distributed;
begin
принять Initialize_Generator (Initiator : in Integer) do
Reset (G, Initiator);
конец Initialize_Generator;
цикл
...
Probability_Of_Event := Random(G);
...
конец цикла;
конец Worker;
begin
-- Инициализировать генераторы в задачах Worker в разных состояниях
для I в W'Range loop
W(I).Initialize_Generator (I);
конец цикла;
... -- Дождаться завершения задач Worker
конец Parallel_Simulation;

ПРИМЕЧАНИЯ

22 Примечания к последнему примеру: Хотя каждая задача Worker инициализирует свой генератор в разном состоянии, эти состояния будут одинаковыми при каждом запуске программы. Состояния генератора можно инициализировать уникально в каждом запуске программы, создав Ada.Numerics.Discrete_Random для типа Integer в основной процедуре, сбросив полученный генератор в зависящее от времени состояние и затем используя случайные целые числа, полученные от этого генератора, для инициализации генераторов в каждой задаче Worker.