Генерация случайных чисел — как из строгости рождается хаос
Случайные числа используются повсюду — создание уникальных миров в компьютерных играх, наука и даже банальные розыгрыши в контакте. Но откуда они берутся?
Конечно, их генерирует компьютер. Но как он это делает? Ведь по сути компьютер умеет выполнять только простые действия — арифметические и логические операции. Нельзя просто сказать машине, что ты от неё хочешь: нужно очень строго это описать
А теперь задумайтесь, как можно используя только строгие указания: какие действия и над какими числами выполнить, получить случайное число? Как получить из порядка хаос?
Но люди предпринимали попытки построить алгоритм, который выдавал бы случайные числа. Например, так выглядит генератор Кнута:
К1. [Выбрать число итераций.] Присвоить Y наибольшую значащую цифру Х. (Мы выполним шаги К2-К13 точно Y+1 раз, т. е. применим рандомизированные преобразования случайное число раз.)
К2. [Выбрать случайный шаг] Присвоить следующую наибольшую значащую цифру X. Переходим к шагу К(3 + Z), т. е. к случайно выбранному шагу в программе.
КЗ. [Обеспечить > 5 х 109] Если X < 5000000000, присвоить X значение X + 5000000000.
К4. [Средина квадрата.] Заменить X серединой квадрата X.
К5. [Умножить.] Заменить X числом (1001001001 X) mod 1010.
К6. [Псевдодополнение.] Если X < 100000000, то присвоить X значение X + 9814055677; иначе присвоить X значение 1010- X.
К7. [Переставить половины.] Поменять местами пять младших по порядку знаков со старшими.
К8. [Умножить.] Выполнить шаг К5.
К9. [Уменьшить цифры.] Уменьшить каждую не равную нулю цифру десятичного представления числа X на единицу.
К10. [Модифицировать на 99999.] Если А' < 105, присвоить X значение — X 2 +99999; иначе присвоить X значение X — 99999.
К11. [Нормировать.] (На этом шаге А' не может быть равным нулю.) Если X <109, то умножить X на 10.
К12. [Модификация метода средин квадратов.] Заменить Х на средние 10 цифр числа Х(Х — 1).
К13. [Повторить?] Если Y > 0, уменьшить У на 1 и возвратиться к шагу К2. Если Y = 0, алгоритм завершен. Значение числа X, полученное на предыдущем шаге, и будет желаемым «случайным» значением.
Он кажется очень сложным и, казалось бы, должен обеспечить случайность. Но на деле эти шаги приводят к получению числа 6065038420, которое зацикливает алгоритм на себя же
Но получать случайные числа оказалось так важно, что люди придумали ещё один метод, назвав его пострашнее, чтобы отпугнуть рекурсию и прочих хакеров. А именно линейный конгруэнтный метод
Давайте возьмём некоторое начальное число. Обзовём его икс нулевое (X0) и дадим ему значение, например, 4. Домножим его на другое число, например, 3, которое назовём множителем и обозначим a. Получится 12
Прибавим ещё одно случайное число, пусть будет 5. Его нужно назвать пострашнее, так как сложение — это слишком простое действие. Допустим, приращением. А обозначим его буквой с
X0*a + c = 4*3 + 5 = 17
Теперь осуществим действие посложнее. Поделим результат на ещё одно число, например, 7. Но возьмём не результат деления, а остаток от него. Это число обозначим буквой m, а операцию деления и взятия остатка символом процента %
17 / 7 = 2 и ещё 3 остаётся в остатке. Это число нам и нужно! Запишем всё вышеизложенное в виде итоговой формулы, а результат назовём икс-первым: X1
X1 = (X0*a + c) % m = (4*3 + 5) % 7 = 17 % 7 = 3
Поздравляю, мы только что изобрели не самый простой способ получения числа 3! Но кроме того, подставляя результат на место X0 в исходную формулу мы можем получить последовательность чисел, которая похожа на случайную! Для таких исходных данных мы получим последовательность:
3, 0, 5, 6, 2, 4, 3, 0, 5, 6, 2, 4, 3, 0…
Выглядит достаточно случайно! Но с определённого момента начинает повторяться. Дело в том, что мы ограничены константой m. Так как мы берём остаток от деления, невозможно получить таким образом больше чисел, чем число, на которое мы делим. Представьте остатки от деления чисел на 3:
1 % 3 = 1
2 % 3 = 2
3 % 3 = 0
4 % 3 = 1
Видно, что последовательность начинает повторяться и, если немного подумать, довольно очевидно, почему
Поэтому на практике используют гораздо большие константы. Например, в языке программирования java это следующие числа:
a = 25214903917
m = 281474976710655
c = 11
Остаётся только задать число X0. Для этого часто используется текущее время: сколько секунд прошло с 1 января 1970 года (программисты порой бывают странными), а также самые разнообразные генераторы энтропии. Это какие-то источники случайных процессов в окружающем мире. Например, испускание электронов радиоактивным элементом, шум собственного компьютера или даже космоса!
Вот такая математика скрывается за каждым розыгрышем вконтакте. По этому поводу шутил математик Роберт Кавью:
Генерация случайных чисел слишком важна, чтобы оставлять её на волю случая
Больше постов о науке и учёбе можно найти в моей группе ВК и канале телеграм