Случайные числа в программировании

Продолжение таблицы 1.1

     

Microsoft CryptoAPI	Текущее время, размер жёсткого диска, размер свободной  памяти, номер процесса	MD5-хеш внутреннего состояния размером в 128 бит	Встроен в Windows, не «застревает»	Сильно зависит  от используемого криптопровайдера (CSP).
Java SecureRandom	Взаимодействие  между потоками	SHA-1-хеш внутреннего состояния (1024 бит)	Большое внутреннее состояние	Медленный сбор энтропии
Chaos от Ruptor	Счётчик тактов процессора, собирается непрерывно	Хеширование 4096-битового внутреннего состояния на основе нелинейного варианта Marsaglia-генератора	Пока самый  быстрый из всех, большое внутреннее состояние, не «застревает»	Оригинальная  разработка, свойства приведены только по утверждению автора
RRAND от Ruptor	Счётчик тактов процессора	Зашифровывание  внутреннего состояния поточным шифром EnRUPT в authenticated encryption режиме	Очень быстр, внутреннее состояние произвольного размера  по выбору, не «застревает»	Шифр не является криптостойким.

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

 

Таблица 1.2– Случайные числа равномерно распределенные от 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
…								…

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

     1.5.Программные ГСЧ

       К программным ГСЧ относятся различные алгоритмы генерирования последовательности чисел, которая по своим характеристикам напоминает случайную. Для формирования очередного числа последовательности используются различные алгебраические преобразования. Одним из первых программных ГСЧ является метод средин квадратов (Среднеквадратичный метод), предложенный в 1946 г. Дж. фон Нейманом. Этот ГСЧ формирует следующий элемент последовательности на основе предыдущего путем возведения его в квадрат и выделения средних цифр полученного числа. Например, мы хотим получить 10-значное число, и предыдущее число равнялось 5772156649. Возводим его в квадрат и получаем 33317792380594909201; значит, следующим числом будет 7923805949. Очевидным недостатком этого метода является зацикливание в случае, если очередное число будет равно нулю.

     Некоторые ученые экспериментировали с методом  середин квадратов в начале 50-х  годов. Работая с четырехзначными  числами вместо десятизначных, Дж.Э. Форсайт испытал 16 различных начальных значений и обнаружил, что 12 из них приводят к циклическим последовательностям, заканчивающимся циклом 6100, 2100, 4100, 8100, 6100,…, в то время как две из них приводят к последовательностям, вырождающимся в 0. более интенсивные исследования, главным образом в двоичной системе счисления, провел Н.К. Метрополис. Он показал, что если использовать 20-разрядное число, то последовательность случайных чисел, полученная методом середин квадратов, вырождается в 13 различных циклов, причем длина самого большого периода равна 142.

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

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

     В настоящий момент наиболее часто  применяется метод генерации  случайных чисел, основывающийся на использовании уравнения или по-другому он называется линейный конгруэнтный метод. Метод довольно старый–1950х годов. Разработал его Деррик Лемер. Этот метод использует следующее уравнение:

 
       При выполнении следующих условий: R>0, a>0, c>0, m>R , a и c.  Отметим, что Rn - это предыдущее число, а Rn+1 - следующее. Данный метод иногда называют линейным сравнительным методом. Формула так проста, что можно подумать, что генерировать случайные числа просто. Однако, это ловушка: насколько хорошо работает данная формула, очень сильно зависит от значения а, с и m. Модуль (m) должен быть довольно большим, так как он определяет область случайных чисел. Операция взятия по модулю порождает остаток от деления числа на модуль. Следовательно, 10 по модулю 4 равно 2. Таким образом, если модуль равен 12, то формулой порождаются числа от 0 до 11, а если модуль равен 21425, то порождаются числа от 0 до 21424. Выбор множителя а и приращения с является очень сложной задачей. В общем случае множитель может быть довольно большим, а приращение - маленьким. Множество попыток и проверок необходимо, чтобы создать хороший генератор.

     В качестве примера рассмотрим один из наиболее часто используемых генераторов случайных чисел. Уравнение, показанное в Rаn1, используется как основа для генератора случайных чисел в ряде популярных языков.  

 var 
      a1: integer;  
    function Ran1: real; 
    var 
      t: real; 
    begin 
      t := (a1*32749+3) mod 32749; 
      a1 := Trunc(t); 
      Ran1 := Abs(t/32749); 
    end;

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

     Во-вторых, начальное значение задается через  глобальную переменную а1. До первого вызова Ran1 переменная а1 должна быть установлена в 1.

В-третьих, в  Ran1 случайные числа делятся на модуль прежде, чем они будут возвращены функцией, для того, чтобы числа лежали в области от 0 до 1. Если поинтересоваться значением глобальной переменной а1 до возврата строки, то оно должно лежать в области от 0 до 32748. Следовательно, когда а1 делится на 32749, полученное число будет больше или равно 0 и меньше 1.

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

var 
      a2:integer; { установить в значение 203 до первого вызова 
                    Ran2 } 
    function Ran2: real; 
    var 
      t: real; 
    begin 
      t := (a2*10001+3) mod 17417; 
      a2 := Trunc(t); 
      Ran2 := Abc(t/17417); 
    end; {Ran2}

     Оба этих генератора случайных чисел  порождают хорошие последовательности случайных чисел.

     Алгоритм Блюма, Блюма  и Шуба (Blum Blum Shub, BBS)

Предложен в 1986 году Ленор и Мануэлем Блюм и  Майклом Шубом.

BBS заключается  в применении следующей формулы:

     x_n+1 = (x_n)² modM          (1.2)

где M=p*q является произведением двух больших простых p и q.

На каждом шаге алгоритма выходные данные получаются из x_n путём взятия либо бита чётности, либо одного или больше наименее значимых бит x_n. И НОД(φ(p-1), φ(q-1)) должен быть мал [14].

     Интересной  особенностью этого алгоритма является то, что для получения x_n необязательно вычислять все n - 1 предыдущих чисел, если известно начальное состояние генератора x₀ и числа p и q. n-ное значение может быть вычислено "напрямую" используя формулу:

                                   (1.3)

     Метод Монте-Карло

     Метод Монте-Карло можно определить как  метод моделирования случайных  величин с целью вычисления характеристик  их распределений.

    Для того чтобы подробнее рассмотреть  этот метод посмотрим дополнительные теоретические сведения:

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

    Математическим  ожиданием дискретной случайной  величины называют сумму произведений всех её возможных значений на их вероятность.

                                  ,

     где Х – случайная величина, - значения, вероятности которых соответственно равны .

     Математическое  ожидание приближённо равно (тем  точнее, чем больше число испытаний) среднему арифметическому наблюдаемых  значений случайной величины.

    Дисперсией (рассеянием) случайной величины называют математическое ожидание квадрата отклонения случайной величины от её математического  ожидания: .

    Средним квадратичным отклонением случайной  величины Х называют квадратный корень из дисперсии: .

    Сущность  метода Монте-Карло состоит в  следующем: требуется найти значение а некоторой изучаемой величины. Для этого выбирают такую случайную величину Х, математическое ожидание которой равно а:

      М(Х)=а.

    Практически же поступают так: производят n испытаний, в результате которых получают n возможных значений Х; вычисляют их среднее арифметическое и принимают x в качестве оценки (приближённого значения) a^*  искомого числа a:

                                              .

     Поскольку метод Монте-Карло требует проведения большого числа испытаний, его часто  называют методом статистических испытаний. Теория этого метода указывает, как  наиболее целесообразно выбрать  случайную величину Х, как найти её возможные значения. В частности, разрабатываются способы уменьшения дисперсии используемых случайных величин, в результате чего уменьшается ошибка, допускаемая при замене искомого математического ожидания а его оценкой а^*.