Как рождается случайность

Случайные числа используются повсюду — создание уникальных миров в компьютерных играх, наука и даже банальные розыгрыши в контакте. Но откуда они берутся?

Конечно, их генерирует компьютер. Но как он это делает? Ведь по сути компьютер умеет выполнять только простые действия — арифметические и логические операции. Нельзя просто сказать машине, что ты от неё хочешь: нужно очень строго это описать

А теперь задумайтесь, как можно используя только строгие указания: какие действия и над какими числами выполнить, получить случайное число? Как получить из порядка хаос?

Но люди предпринимали попытки построить алгоритм, который выдавал бы случайные числа. Например, так выглядит генератор Кнута:

К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 года (программисты порой бывают странными), а также самые разнообразные генераторы энтропии. Это какие-то источники случайных процессов в окружающем мире. Например, испускание электронов радиоактивным элементом, шум собственного компьютера или даже космоса!

Вот такая математика скрывается за каждым розыгрышем вконтакте. По этому поводу шутил математик Роберт Кавью:

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

Спасибо за чтение! Наш телеграм канал

Источник: m.vk.com

Комментарии: