Генерация псевдослучайных чисел

«Генерация случайных чисел слишком важна, чтобы оставлять её на волю случая»
Роберт Р. Кавью

ОПРЕДЕЛЕНИЕ

Генерация псевдослучайных чисел — порождение последовательности чисел, элементы которой подчиняются заданному распределению (обычно равномерному).

Псевдослучайные числа используются в методе Монте-Карло, в криптографии, для моделирования физической и игровой реальности, для придания действиям игрового искусственного интеллекта элемента спонтанности.

Соответствующие алгоритмы называют генераторами псевдослучайных чисел (ГПСЧ).

ДЕТЕРМИНИРОВАННЫЕ ГЕНЕРАТОРЫ

Детерминированный алгоритм не может генерировать полностью случайные числа, он может только аппроксимировать некоторые их свойства.

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

Большинство простых арифметических генераторов имеют недостатки:

· Слишком короткий период.

· Последовательные значения не являются независимыми.

· Некоторые биты «менее случайны», чем другие.

· Неравномерное одномерное распределение.

· Обратимость.

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

Члены последовательности вычисляются рекуррентно по формуле:

Xk+1=(aXk+c)mod m

где a и c — некоторые целочисленные коэффициенты, а mod m — взятие остатка по модулю некоторого натурального числа m.

1. НОД(c,m)=1 (то есть, c и m взаимно просты);

2. a−1 кратно p для всех простых делителей p числа m;

3. a−1 кратно 4, если m кратно 4.

длина периода меньше либо равна m.

ЧАСТО ИСПОЛЬЗУЕМЫЕ ПАРАМЕТРЫ

1. m=232,a=69069,c=5

2. m=232,a=22695477,c=1

3. m=232,a=1664525,c=1013904223

4. m=264,a=6364136223846793005,c=1442695040888963407

Линейный конгруэнтный метод дает статистически приемлемое распределение псевдослучайных чисел, но не является криптостойким.

Реализация линейного конгруэнтного метода на Си

unsigned long g_random_seed = 1; //глобальная переменная с последним числом

unsigned long my_rand()
{
//размер unsigned long равен 4 байта!
//m = 2^32
return g_random_seed = 69069LU*g_random_seed + 5LU;
}

Реализация линейного конгруэнтного метода на Python

g_random_seed = 1
def rr():
global g_random_seed
g_random_seed = (69069*g_random_seed+5)%(2**32)

ВОПРОС

Почему в алгоритме на Си отсутствует деление по модулю m, но код работает, а в Python наличие %(2**32)обязательно?

ОТВЕТ

В языке Python реализована длинная арифметика, и целые числа могут быть произвольной длины, а в Си размер числа ограничен количеством бит, отведенных под него.

При этом unsigned long int имеет размер 4 байта — это 32 бита, следовательно результаты операций сложения и умножения в Си для типа unsigned long int и так всегда будут происходить по модулю 232.

Рекурсия в Python

Функции могут вызывать и другие функции, и даже вызывать сами себя! Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что 0!=1, 1!=1. А как вычислить величину n! для большого n? Если бы мы могли вычислить величину (n−1)!, то тогда мы легко вычислим n!, поскольку n!=n(n−1)!. Но как вычислить (n−1)!? Если бы мы вычислили (n−2)!, то мы сможем вычисли и (n−1)!=(n−1)(n−2)!. А как вычислить (n−2)!? Если бы… В конце концов, мы дойдем до величины 0!, которая равна 1. Таким образом, для вычисления факториала мы можем использовать значение факториала для меньшего числа. Это можно сделать и в программе на Питоне:

def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)

Подобный прием (вызов функцией самой себя) называется рекурсией, а сама функция называется рекурсивной.

Как это работает? Допустим, мы вызвали функцию factorial(4). Будет вызвана функция, у которой значение параметра n==4. Она проверит условие n==0, поскольку условие ложно, то будет выполнена инструкция return n∗factorial(n−1). Но чтобы вычислить это значение, будет вызвана функция factorial(3), т. к. параметр n имеет значение, равное 4. Теперь в памяти будет находиться две функции factorial — одна со значением параметра n==4, а другая — n==3. При этом активна будет последняя функция.

Эта функция в свою очередь вызовет функцию factorial(2), та вызовет функцию factorial(1), затем factorial(0). В случае этой функции ничего более вызвано не будет, функция просто вернет значение 1, и управление вернется в функцию factorial(1). Та умножит значение n==1 на значение 1, которое вернула функция factorial(0), и вернет полученное произведение, равное 1. Управление вернется в функцию factorial(2), которая умножит n==2 на значение 1, которое вернула функция factorial(1) и вернет полученное произведение, равное 2. Функция factorial(3) вернет 3∗2==6, а функция factorial(4) вернет 4∗6==24.

Таблица последовательности, в которой будут вызываться функции, приведена ниже. Значения функции возвращают в порядке, обратном порядке их вызова, то есть сначала заканчивает работу функция factorial(0), затем factorial(1) и т. д.

С какими параметрами вызвана функция	Какое значение вернула
factorial(4)	4 * 6 == 24
factorial(3)	3 * 2 == 6
factorial(2)	2 * 1 == 2
factorial(1)	1 * 1 == 1
factorial(0)

 

При отладке программы всю последовательность вложенных вызовов рекуррентных функций можно изучить в окне «Call Stack» («стек вызовов») в режиме отладки среды Wing IDE. При этом значения локальных переменных будут отображаться в окне «Stack data», и для каждой вызываемой функции значения локальных переменных будут своими.

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

1. Какой случай (для какого набора параметров) будет крайним (простым) и что функция возвращает в этом случае?

2. Как свести задачу для какого-то набора параметров (за исключением крайнего случая) к задаче, для другого набора параметров (как правило, с меньшими значениями)?

При этом программирование рекурсии выглядит так. Функция должна сначала проверить, не является ли переданный набор параметров простым (крайним) случаем. В этом случае функция должна вернуть значение (или выполнить действия), соответствующие простому случаю. Иначе функция должна вызвать себя рекурсивно для другого набора параметров, и на основе полученных значений вычислить значение, которое она должна вернуть.

Рассмотрим несколько примеров (на самом деле эти примеры являются «учебными» и все перечисленные задачи гораздо лучше решать при помощи циклов, а не рекурсией).