Справочник Ada 95
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;
function Random (Gen : Generator) return Uniformly_Distributed;
procedure Reset (Gen : in Generator;
Initiator : in Integer);
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);
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;
function Value (Coded_State : String) return State;
private
... -- не определено языком
end Ada.Numerics.Float_Random;
... -- не определено языком
end Ada.Numerics.Float_Random;
Обобщённый библиотечный пакет 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);
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);
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;
function Value (Coded_State : String) return State;
private
... -- не определено языком
end Ada.Numerics.Discrete_Random;
... -- не определено языком
end Ada.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;
Получает «следующее» случайное число из данного генератора относительно его текущего состояния в соответствии с определённым реализацией алгоритмом. Результат функции в 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 : 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, приблизительно равномерно распределена по диапазону подтипа результата.
Функция Random в экземпляре Numerics.Discrete_Random гарантированно возвращает каждое значение в своём подтипе результата за конечное число вызовов, при условии, что количество таких значений не превышает 215.
Другие требования к производительности генератора случайных чисел, которые применяются только в реализациях, соответствующих Приложению Numerics, и только в режиме «строго» (см. G.2), приведены в G.2.5.
Требования к документации
Не существует одного алгоритма генерации случайных чисел, который был бы наилучшим для всех применений. Для того, чтобы пользователь мог определить пригодность генераторов случайных чисел для предполагаемого применения, реализация должна описать используемый алгоритм и должна указать его период, если он известен точно, или нижнюю границу периода, если точный период неизвестен. Периоды, которые настолько длинны, что периодичность неощутима на практике, могут быть описаны таким образом, без приведения числовой границы.
Реализация также должна задокументировать минимальный интервал времени между вызовами процедуры Reset, зависящей от времени, которая гарантированно инициирует разные последовательности, и она должна задокументировать характер строк, которые Value будет принимать без вызова Constraint_Error.
Рекомендации по реализации
Любая память, связанная с объектом типа Generator, должна быть освобождена при выходе из области видимости объекта.
Если период генератора достаточно велик по отношению к количеству различных значений инициализатора, то каждое возможное значение Initiator, переданное в Reset, должно инициировать последовательность случайных чисел, которая практически не перекрывает последовательность, инициированную любым другим значением. Если это невозможно, то отображение между значениями инициализатора и состояниями генератора должно быть быстро меняющейся функцией значения инициализатора.
ПРИМЕЧАНИЯ
14 Если две или более задачи должны использовать один и тот же генератор, то задачи должны синхронизировать свой доступ к генератору так же, как и к любой общей переменной (см. 9.10).
15 В рамках данного имплементирования, повторяющуюся последовательность случайных чисел можно получить, полагаясь на неявную инициализацию генераторов или явно инициализируя генератор с помощью повторяемого начального значения. Различные последовательности случайных чисел могут быть получены от данного генератора в различных выполнениях программы путём явной инициализации генератора до состояния, зависящего от времени.
16 Данная реализация функции Random в Numerics.Float_Random может или не может быть способна возвращать значения 0.0 или 1.0. Переносимые приложения должны предполагать, что эти значения или значения, достаточно близкие к ним, чтобы вести себя неотличимо, могут возникать. Если требуется последовательность случайных целых чисел из некоторого фиксированного диапазона, приложение должно использовать функцию Random в соответствующей инстанциации Numerics.Discrete_Random, а не преобразовывать результат функции Random в Numerics.Float_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 возвращает ненулевое значение.
Примеры
Пример программы, которая играет в симулированную игру в кости:
with Ada.Numerics.Discrete_Random;
procedure Dice_Game is
subtype Die is Integer range 1 .. 6;
subtype Dice is Integer range 2*Die'First .. 2*Die'Last;
package Random_Die is new Ada.Numerics.Discrete_Random (Die);
use Random_Die;
G : Generator;
D : Dice;
begin
Reset (G); -- Инициализировать генератор в уникальном состоянии в каждом запуске
loop
-- Бросить пару костей; суммировать и обработать результаты
D := Random(G) + Random(G);
...
end loop;
end Dice_Game;
procedure Dice_Game is
subtype Die is Integer range 1 .. 6;
subtype Dice is Integer range 2*Die'First .. 2*Die'Last;
package Random_Die is new Ada.Numerics.Discrete_Random (Die);
use Random_Die;
G : Generator;
D : Dice;
begin
Reset (G); -- Инициализировать генератор в уникальном состоянии в каждом запуске
loop
-- Бросить пару костей; суммировать и обработать результаты
D := Random(G) + Random(G);
...
end loop;
end Dice_Game;
Пример программы, которая имитирует подбрасывание монеты:
with Ada.Numerics.Discrete_Random;
procedure Flip_A_Coin is
type Coin is (Heads, Tails);
package Random_Coin is new Ada.Numerics.Discrete_Random (Coin);
use Random_Coin;
G : Generator;
begin
Reset (G); -- Инициализировать генератор в уникальном состоянии в каждом запуске
loop
-- Подбросить монету и обработать результат
case Random(G) is
when Heads =>
...
when Tails =>
...
end case;
...
end loop;
end Flip_A_Coin;
procedure Flip_A_Coin is
type Coin is (Heads, Tails);
package Random_Coin is new Ada.Numerics.Discrete_Random (Coin);
use Random_Coin;
G : Generator;
begin
Reset (G); -- Инициализировать генератор в уникальном состоянии в каждом запуске
loop
-- Подбросить монету и обработать результат
case Random(G) is
when Heads =>
...
when Tails =>
...
end case;
...
end loop;
end Flip_A_Coin;
Пример параллельной симуляции физической системы, с отдельным генератором вероятностей событий в каждой задаче:
with Ada.Numerics.Float_Random;
procedure Parallel_Simulation is
use Ada.Numerics.Float_Random;
task type Worker is
entry Initialize_Generator (Initiator : in Integer);
...
end Worker;
W : array (1 .. 10) of Worker;
task body Worker is
G : Generator;
Probability_Of_Event : Uniformly_Distributed;
begin
accept Initialize_Generator (Initiator : in Integer) do
Reset (G, Initiator);
end Initialize_Generator;
loop
...
Probability_Of_Event := Random(G);
...
end loop;
end Worker;
begin
-- Инициализировать генераторы в задачах Worker в различных состояниях
for I in W'Range loop
W(I).Initialize_Generator (I);
end loop;
... -- Ожидание завершения задач Worker
end Parallel_Simulation;
procedure Parallel_Simulation is
use Ada.Numerics.Float_Random;
task type Worker is
entry Initialize_Generator (Initiator : in Integer);
...
end Worker;
W : array (1 .. 10) of Worker;
task body Worker is
G : Generator;
Probability_Of_Event : Uniformly_Distributed;
begin
accept Initialize_Generator (Initiator : in Integer) do
Reset (G, Initiator);
end Initialize_Generator;
loop
...
Probability_Of_Event := Random(G);
...
end loop;
end Worker;
begin
-- Инициализировать генераторы в задачах Worker в различных состояниях
for I in W'Range loop
W(I).Initialize_Generator (I);
end loop;
... -- Ожидание завершения задач Worker
end Parallel_Simulation;
ПРИМЕЧАНИЯ
17 Примечания к последнему примеру: Несмотря на то, что каждая задача Worker инициализирует свой генератор в разном состоянии, эти состояния будут одинаковыми в каждом выполнении программы. Состояния генератора могут быть уникально инициализированы в каждом выполнении программы путём инстанцирования Ada.Numerics.Discrete_Random для типа Integer в основной процедуре, сброса генератора, полученного от этой инстанции, до состояния, зависящего от времени, и последующего использования случайных целых чисел, полученных от этого генератора, для инициализации генераторов в каждой задаче Worker.
