Статистическое исследование свойств псевдослучайных чисел получаемых методом Джона фон Неймана

курсовая работа

Способы получения псевдослучайных чисел. Генератор псевдослучайных чисел Джона фон Неймана

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

тестирование алгоритмов;

имитационное моделирование;

некоторые задачи численного анализа;

имитация пользовательского ввода.

Устройства или алгоритмы получения случайных чисел называют генераторами случайных чисел или датчиками случайных чисел.

Для получения случайных чисел можно использовать различные способы. В общем случае все методы генерирования случайных чисел (ГСЧ) можно разделить на следующие:

физические

табличные

алгоритмические.

Физические ГСЧ

Примером физических ГСЧ могут служить: монета («орел» -- 1, «решка» -- 0); игральные кости; поделенный на секторы с цифрами барабан со стрелкой; аппаратурный генератор шума, в качестве которого используют шумящее тепловое устройство, например, транзистор.

Табличные ГСЧ

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

Таблица 1.

Равномерно распределенные от 0 до 1 случайные числа

Случайные цифры

Равномерно распределенные от 0 до 1 случайные числа

9

2

9

2

0

4

2

6

0.929

9

5

7

3

4

9

0

3

0.204

5

9

1

6

6

5

7

6

0.269

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

Алгоритмические ГСЧ

Числа, генерируемые с помощью этих ГСЧ, всегда являются псевдослучайными, то есть каждое последующее сгенерированное число зависит от предыдущего:

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

Достоинством данных ГСЧ является быстродействие; генераторы практически не требуют ресурсов памяти, компактны. Недостатки: числа нельзя в полной мере назвать случайными, поскольку между ними имеется зависимость, а также наличие периодов в последовательности псевдослучайных чисел.

К алгоритмическим методам получения ГСЧ относиться метод серединных квадратов, предложенный в 1946 г. Дж. фон Нейманом.

Метод серединных квадратов

Имеется некоторое четырехзначное число R0. Это число возводится в квадрат и заносится в R1. Далее из R1 берется середина (четыре средних цифры) -- новое случайное число -- и записывается в R0. Затем процедура повторяется . Отметим, что на самом деле в качестве случайного числа необходимо брать не ghij, а 0.ghij -- с приписанным слева нулем и десятичной точкой. Поясним его на примере. Пусть задано 4-значное целое число n1 = 9876. Возведем его в квадрат. Получим, вообще говоря, 8-значное число 97 535 376. Выберем четыре средние цифры из этого числа и обозначим n2 = 5353. Затем возведем его в квадрат (28 654 609) и снова извлечем 4 средние цифры. Получим n3 = 6546. Далее, 42 850116, n4 = 8501 и т. д. В качестве значений случайной величины предлагается использовать значения 0,9876; 0,5353; 0,6546; 0,8501; 0,2670; 0,1289.

Недостатки метода:

1) если на некоторой итерации число R0 станет равным нулю, то генератор вырождается, поэтому важен правильный выбор начального значения R0;

2) генератор будет повторять последовательность через Mn шагов (в лучшем случае), где n -- разрядность числа R0, M -- основание системы счисления.

Для примера : если число R0 будет представлено в двоичной системе счисления, то последовательность псевдослучайных чисел повторится через 24 = 16 шагов. Заметим, что повторение последовательности может произойти и раньше, если начальное число будет выбрано неудачно.

Делись добром ;)