Руководство по Ada (Ada 2022)
A.5.2 Генерация случайных чисел
Средства для генерации псевдослучайных чисел с плавающей точкой предоставляются в пакете Numerics.Float_Random; обобщенный пакет Numerics.Discrete_Random предоставляет аналогичные средства для генерации псевдослучайных целых чисел и псевдослучайных значений типов перечисления. Для краткости, псевдослучайные значения любого из этих типов называются случайными числами.
Некоторые из предоставляемых средств являются базовыми для всех применений случайных чисел. К ним относятся ограниченный частный тип, каждый объект которого служит генератором последовательности (возможно, отличной) случайных чисел; функция получения «следующего» случайного числа из заданной последовательности случайных чисел (то есть, из ее генератора); и подпрограммы инициализации или повторной инициализации заданного генератора до состояния, зависящего от времени, или состояния, обозначаемого одним целым числом.
Другие средства предоставляются специально для продвинутых применений. К ним относятся подпрограммы для сохранения и восстановления состояния заданного генератора; частный тип, объекты которого могут использоваться для хранения сохраненного состояния генератора; и подпрограммы получения строкового представления заданного состояния генератора или, заданного такого строкового представления, соответствующего состояния.
Статическая семантика
Библиотечный пакет Numerics.Float_Random имеет следующее объявление:
package Ada.Numerics.Float_Random
with Global => in out synchronized is
with Global => in out synchronized is
-- Основные средства
type Generator is limited private;
subtype Uniformly_Distributed is Float range 0.0 .. 1.0;
function Random (Gen : Generator) return Uniformly_Distributed
with Global => overriding in out Gen;
function Random (Gen : Generator) return Uniformly_Distributed
with Global => overriding in out Gen;
procedure Reset (Gen : in Generator;
Initiator : in Integer)
with Global => overriding in out Gen;
procedure Reset (Gen : in Generator)
with Global => overriding in out Gen;
Initiator : in Integer)
with Global => overriding in out Gen;
procedure Reset (Gen : in Generator)
with Global => overriding in out Gen;
-- Дополнительные средства
type State is private;
procedure Save (Gen : in Generator;
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State)
with Global => overriding in out Gen;
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State)
with Global => overriding in out Gen;
Max_Image_Width : constant := определяемое реализацией целое значение;
function Image (Of_State : State) return String;
function Value (Coded_State : String) return State;
function Value (Coded_State : String) return State;
private
... -- не определено языком
end Ada.Numerics.Float_Random;
... -- не определено языком
end Ada.Numerics.Float_Random;
Тип Generator требует финализации (см. 7.6).
Обобщенный библиотечный пакет Numerics.Discrete_Random имеет следующее объявление:
generic
type Result_Subtype is (<>);
package Ada.Numerics.Discrete_Random
with Global => in out synchronized is
type Result_Subtype is (<>);
package Ada.Numerics.Discrete_Random
with Global => in out synchronized is
-- Основные средства
type Generator is limited private;
function Random (Gen : Generator) return Result_Subtype
with Global => overriding in out Gen;
with Global => overriding in out Gen;
function Random (Gen : Generator;
First : Result_Subtype;
Last : Result_Subtype) return Result_Subtype
with Post => Random'Result in First .. Last,
Global => overriding in out Gen;
First : Result_Subtype;
Last : Result_Subtype) return Result_Subtype
with Post => Random'Result in First .. Last,
Global => overriding in out Gen;
procedure Reset (Gen : in Generator;
Initiator : in Integer)
with Global => overriding in out Gen;
procedure Reset (Gen : in Generator)
with Global => overriding in out Gen;
Initiator : in Integer)
with Global => overriding in out Gen;
procedure Reset (Gen : in Generator)
with Global => overriding in out Gen;
-- Дополнительные средства
type State is private;
procedure Save (Gen : in Generator;
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State)
with Global => overriding in out Gen;
To_State : out State);
procedure Reset (Gen : in Generator;
From_State : in State)
with Global => overriding in out Gen;
Max_Image_Width : constant := определяемое реализацией целое значение;
function Image (Of_State : State) return String;
function Value (Coded_State : String) return State;
function Value (Coded_State : String) return State;
private
... -- не определено языком
end Ada.Numerics.Discrete_Random;
... -- не определено языком
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;
function Random (Gen : Generator) return Result_Subtype;
Получает «следующее» случайное число из данного генератора, относительно его текущего состояния, согласно алгоритму, определяемому реализацией.
function Random (Gen : Generator;
First : Result_Subtype;
Last : Result_Subtype) return Result_Subtype
with Post => Random'Result in First .. Last;
First : Result_Subtype;
Last : Result_Subtype) return Result_Subtype
with Post => Random'Result in First .. Last;
Получает «следующее» случайное число из данного генератора, относительно его текущего состояния, согласно алгоритму, определяемому реализацией. Если диапазон First .. Last является пустым диапазоном, то генерируется исключение Constraint_Error.
procedure Reset (Gen : in Generator;
Initiator : in Integer);
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);
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;
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 имеет диапазон результатов; это диапазон First .. Last для версии Random с параметрами First и Last и диапазон подтипа результата функции в противном случае.
Достаточно длинная последовательность случайных чисел, полученная последовательными вызовами Random с тем же генератором и диапазоном результатов, примерно равномерно распределена по диапазону результатов.
Функция Random в инстанциации Numerics.Discrete_Random гарантированно возвращает каждое значение в ее диапазоне результатов за конечное число вызовов, при условии, что число таких значений не превышает 215.
Другие требования к производительности генератора случайных чисел, которые применяются только в реализациях, соответствующих приложению Numerics, и только в «строгом» режиме, определенном там (см. G.2), приведены в G.2.5.
Требования к документации
Для всех приложений не существует одного наилучшего алгоритма генерации случайных чисел. Чтобы пользователь мог определить применимость генераторов случайных чисел для конкретного приложения, в реализации должен быть описан используемый алгоритм и его период, если он точно известен, или нижняя граница периода, если точный период неизвестен. Периоды, настолько длинные, что периодичность практически неопределима, могут быть описаны в таких терминах, без приведения численной границы.
В реализации также должна быть задокументирована минимальная временная задержка между вызовами процедуры сброса, зависящей от времени, которая гарантирует инициирование различных последовательностей, а также природа строк, которые функция Value может принять без повышения Constraint_Error.
Рекомендации по реализации
Любая память, связанная с объектом типа Generator, должна быть освобождена при выходе из области видимости объекта.
Если период генератора достаточно велик по отношению к количеству различных значений инициализатора, то каждое возможное значение Initiator, переданное в Reset, должно инициировать последовательность случайных чисел, которая практически не перекрывается с последовательностью, инициированной любым другим значением. Если это невозможно, то отображение между значениями инициализатора и состояниями генератора должно быть быстро меняющейся функцией от значения инициализатора.
ПРИМЕЧАНИЕ 1 Если две или более задачи используют один и тот же генератор, то задачи должны синхронизировать свой доступ к генератору, как и к любой общей переменной (см. 9.10).
ПРИМЕЧАНИЕ 2 В рамках данной реализации повторяющаяся последовательность случайных чисел может быть получена, полагаясь на неявную инициализацию генераторов или явную инициализацию генератора с повторяющимся значением инициализатора. Разные последовательности случайных чисел могут быть получены от данного генератора в различных запусках программы путём явной инициализации генератора в состояние, зависящем от времени.
ПРИМЕЧАНИЕ 3 Данная реализация функции Random в Numerics.Float_Random не гарантирует возможности получения значений 0.0 или 1.0. Приложения будут более портативными, если они предполагают, что эти значения, или значения, достаточно близкие к ним, чтобы быть неотличимыми от них, могут встречаться. Если требуется последовательность случайных целых чисел из некоторого диапазона, приложение должно использовать одну из функций Random в соответствующей инстанциации Numerics.Discrete_Random, а не преобразовывать результат функции Random в Numerics.Float_Random.
Этот абзац был удален.
ПРИМЕЧАНИЕ 4 Случайные числа (с плавающей точкой) с экспоненциальным распределением и средним и стандартным отклонением 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 есть
подтип Die есть Целое число диапазон 1 .. 6;
подтип Dice есть Целое число диапазон 2*Die'First .. 2*Die'Last;
пакет Random_Die есть новый Ada.Numerics.Discrete_Random (Die);
используется Random_Die;
G : Генератор;
D : Dice;
начать
Reset (G); -- Начать генератор в уникальном состоянии при каждом запуске
цикл
-- Бросить пару костей; суммировать и обработать результаты
D := Random(G) + Random(G);
...
конец цикла;
конец Dice_Game;
процедура Dice_Game есть
подтип Die есть Целое число диапазон 1 .. 6;
подтип Dice есть Целое число диапазон 2*Die'First .. 2*Die'Last;
пакет Random_Die есть новый Ada.Numerics.Discrete_Random (Die);
используется Random_Die;
G : Генератор;
D : Dice;
начать
Reset (G); -- Начать генератор в уникальном состоянии при каждом запуске
цикл
-- Бросить пару костей; суммировать и обработать результаты
D := Random(G) + Random(G);
...
конец цикла;
конец Dice_Game;
Пример программы, имитирующей подбрасывание монеты:
с Ada.Numerics.Discrete_Random;
процедура Flip_A_Coin есть
тип Coin есть (Орёл, Решка);
пакет Random_Coin есть новый Ada.Numerics.Discrete_Random (Coin);
используется Random_Coin;
G : Генератор;
начать
Reset (G); -- Начать генератор в уникальном состоянии при каждом запуске
цикл
-- Подбросить монету и обработать результат
случай Random(G) есть
когда Орёл =>
...
когда Решка =>
...
конец случая;
...
конец цикла;
конец Flip_A_Coin;
процедура Flip_A_Coin есть
тип Coin есть (Орёл, Решка);
пакет Random_Coin есть новый Ada.Numerics.Discrete_Random (Coin);
используется Random_Coin;
G : Генератор;
начать
Reset (G); -- Начать генератор в уникальном состоянии при каждом запуске
цикл
-- Подбросить монету и обработать результат
случай Random(G) есть
когда Орёл =>
...
когда Решка =>
...
конец случая;
...
конец цикла;
конец Flip_A_Coin;
Пример параллельной симуляции физической системы, с отдельным генератором вероятностей событий в каждой задаче:
с Ada.Numerics.Float_Random;
процедура Parallel_Simulation есть
используется Ada.Numerics.Float_Random;
задача тип Worker есть
вход Initialize_Generator (Initiator : вход Целое число);
...
конец Worker;
W : массив (1 .. 10) из Worker;
задача тело Worker есть
G : Генератор;
Probability_Of_Event : Равномерно_Распределенный;
начать
принять Initialize_Generator (Initiator : вход Целое число) делать
Reset (G, Initiator);
конец Initialize_Generator;
цикл
...
Probability_Of_Event := Random(G);
...
конец цикла;
конец Worker;
начать
-- Инициализировать генераторы в задачах Worker в различных состояниях
для I в W'Range делать
W(I).Initialize_Generator (I);
конец цикла;
... -- Дождаться завершения задач Worker
конец Parallel_Simulation;
процедура Parallel_Simulation есть
используется Ada.Numerics.Float_Random;
задача тип Worker есть
вход Initialize_Generator (Initiator : вход Целое число);
...
конец Worker;
W : массив (1 .. 10) из Worker;
задача тело Worker есть
G : Генератор;
Probability_Of_Event : Равномерно_Распределенный;
начать
принять Initialize_Generator (Initiator : вход Целое число) делать
Reset (G, Initiator);
конец Initialize_Generator;
цикл
...
Probability_Of_Event := Random(G);
...
конец цикла;
конец Worker;
начать
-- Инициализировать генераторы в задачах Worker в различных состояниях
для I в W'Range делать
W(I).Initialize_Generator (I);
конец цикла;
... -- Дождаться завершения задач Worker
конец Parallel_Simulation;
Хотя каждая задача Worker инициализирует свой генератор в разном состоянии, эти состояния будут одинаковыми при каждом выполнении программы. Состояния генератора можно инициализировать уникально в каждом выполнении программы, инстанцируя Ada.Numerics.Discrete_Random для типа Integer в основной процедуре, сбрасывая полученный генератор в состояние, зависящее от времени, и затем используя случайные целые числа, полученные от этого генератора, для инициализации генераторов в каждой задаче Worker.
