Алгоритмы генераторов псевдослучайных чисел

Случайные числа не случайны

Вы когда-нибудь задумывались, как работает Math.random()? Что такое случайное число и как оно получается? А представьте вопрос на собеседовании — напишите свой генератор случайных чисел в пару строк кода. И так, что же это такое, случайность и возможно ли ее предсказать.

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

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

Этот источник используется для накопления энтропии с последующим получением из неё начального значения (initial value, seed), которое необходимо генераторам случайных чисел (ГСЧ) для формирования случайных чисел.

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

Энтропия — это мера беспорядка. Информационная энтропия — мера неопределённости или непредсказуемости информации.

Выходит, что чтобы создать псевдослучайную последовательность нам нужен алгоритм, который будет генерить некоторую последовательность на основании определенной формулы. Но такую последовательность можно будет предсказать. Тем не менее, давайте пофантазируем, как бы могли написать свой генератор случайных чисел, если бы у нас не было Math.random()

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

Придумываем алгоритм ГПСЧ

Генератор псевдослучайных чисел (ГПСЧ, англ. pseudorandom number generator, PRNG) — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

Мы можем взять последовательность каких-то чисел и брать от них модуль числа. Самый простой пример, который приходит в голову. Нам нужно подумать, какую последовательность взять и модуль от чего. Если просто в лоб от 0 до N и модуль 2, то получится генератор 1 и 0:

Эта функция генерит нам последовательность 01010101010101… и назвать ее даже псевдослучайной никак нельзя. Чтобы генератор был случайным, он должен проходить тест на следующий бит. Но у нас не стоит такой задачи. Тем не менее даже без всяких тестов мы можем предсказать следующую последовательность, значит такой алгоритм в лоб не подходит, но мы в нужном направлении.

А что если взять какую-то известную, но нелинейную последовательность, например число PI. А в качестве значения для модуля будем брать не 2, а что-то другое. Можно даже подумать на тему меняющегося значения модуля. Последовательность цифр в числе Pi считается случайной. Генератор может работать, используя числа Пи, начиная с какой-то неизвестной точки. Пример такого алгоритма, с последовательностью на базе PI и с изменяемым модулем:

Но в JS число PI можно вывести только до 48 знака и не более. Поэтому предсказать такую последовательность все так же легко и каждый запуск такого генератора будет выдавать всегда одни и те же числа. Но наш генератор уже стал показывать числа от 0 до 9. Кстати, так выглядит распределение по выпадению чисел при 10000 итерациях:

Распределение очень неравномерное, но мы получим генератор чисел от 0 до 9.

Мы можем взять не число Pi, а время в числовом представлении и это число рассматривать как последовательность цифр, причем для того, чтобы каждый раз последовательность не повторялась, мы будем считывать ее с конца. Итого наш алгоритм нашего ГПСЧ будет выглядеть так:

Вот это уже похоже на генератор псевдослучайных чисел. И тот же Math.random() — это ГПСЧ, про него мы поговорим чуть позже. При этом у нас каждый раз первое число получается разным.

Собственно на этих простых примерах можно понять как работают более сложные генераторы случайных числе. И есть даже готовые алгоритмы. Для примера разберем один из них — это Линейный конгруэнтный ГПСЧ(LCPRNG).

Линейный конгруэнтный ГПСЧ

Линейный конгруэнтный ГПСЧ(LCPRNG) — это распространённый метод для генерации псевдослучайных чисел. Он не обладает криптографической стойкостью. Этот метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:

где a(multiplier), c(addend), m(mask) — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа — т.е. seed. При разных значениях seed получаются различные последовательности случайных чисел. Пример реализации такого алгоритма на JavaScript:

Многие языки программирования используют LСPRNG (но не именно такой алгоритм(!)).

Как говорилось выше, такую последовательность можно предсказать. Так зачем нам ГПСЧ? Если говорить про безопасность, то ГПСЧ — это проблема. Если говорить про другие задачи, то эти свойства — могут сыграть в плюс. Например для различных спец эффектов и анимаций графики может понадобиться частый вызов random. И вот тут важны распределение значений и перформанс! Секурные алгоритмы не могут похвастать скоростью работы.

Еще одно свойство — воспроизводимость. Некоторые реализации позволяют задать seed, и это очень полезно, если последовательность должна повторяться. Воспроизведение нужно в тестах, например. И еще много других вещей существует, для которых не нужен безопасный ГСЧ.

Как устроен Math.random()

Метод Math.random() возвращает псевдослучайное число с плавающей запятой из диапазона [0, 1) , то есть, от 0 (включительно) до 1 (но не включая 1), которое затем можно отмасштабировать до нужного диапазона. Реализация сама выбирает начальное зерно для алгоритма генерации случайных чисел; оно не может быть выбрано или сброшено пользователем.

Как устроен алгоритм Math.random() — интересный вопрос. До недавнего времени, а именно до 49 Chrome использовался алгоритм MWC1616:

Именно этот алгоритм генерит нам последовательность псевдослучайных чисел в промежутке между 0 и 1.

UPD

Исправил ошибку в алгоритме MWC1616 (пропущенные скобки). Эта же ошибка повторяется и в статье https://v8project.blogspot.ru/2015/12/theres-mathrandom-and-then-theres.html

то видим, что должны быть скобки:

Предсказываем Math.random()

Чем это было чревато? Есть такой квест: https://alf.nu/ReturnTrue

В нем есть задача:

Что нужно вписать вместо вопросов, чтобы функция вернула true? Кажется что это невозможно. Но, это возможно, если вы заглядывали в спеку и видели алгоритм ГПСЧ V8. Решение этой задачи в свое время мне показал Роман Дворнов:

Этот код работал в 70% случаев для Chrome < 49 и Node.js < 5. Рома Дворнов, как всегда, показал чудеса магии, которая не что иное, как глубокое понимание внутренних механизмов браузеров. Я все жду, когда Роман сделает доклад на основе этих событий или напишет более подробную статью.

Что здесь происходит? Все дело в том, что алгоритм можно предсказать. Чтобы это было нагляднее, можно сгенерировать картинку случайных пикселей. На сайте https://bl.ocks.org/mmalone/bf59aa2e44c44dde78ac

есть такой генератор. Вот что было, когда в браузере был алгоритм MWC1616:

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

Выходит что мы можем отреверсить Math.random() и предсказать, какое было загадано число на основе того, что получили в данный момент времени. Для этого получаем два значения через Math.random(). Затем вычисляем внутреннее состояние по этим значениям. Имея внутреннее состояние можем предсказывать следующие значения Math.random() при этом не меняя внутреннее состояние. Меняем код так так, чтобы вместо следующего возвращалось предыдущее значение. Собственно все это и описано в коде-решении для задачи random4. Но потом алгоритм изменили (подробности читайте в спеке). Его можно будет сломать, как только у нас в JS появится нормальная работа с 64 битными числами. Но это уже будет другая история.

Новый алгоритм выглядит так:

Его все так же можно будет просчитать и предсказать. Но пока у нас нет “длинной математики” в JS. Можно попробовать через TypedArray сделать или использовать специальные библиотеки. Возможно кто-то однажды снова напишет предсказатель. Возможно это будешь ты, читатель. Кто знает ?

Сrypto Random Values

Метод Math.random() не предоставляет криптографически стойкие случайные числа. Не используйте его ни для чего, связанного с безопасностью. Вместо него используйте Web Crypto API (API криптографии в вебе) и более точный метод window.crypto.getRandomValues() .

Пример генерации случайного числа:

Но, в отличие от ГПСЧ Math.random(), этот метод очень ресурсоемкий. Дело в том, что данный генератор использует системные вызовы в ОС, чтобы получить доступ к источникам энтропии (мак адрес, цпу, температуре, etc…).

Материалы про Math.random()

Больше про random в спецификации:

Хорошая статья про работу рандомайзера

Пример реализации предсказателя с Math.random()

Кстати, следить за обновлениями и прочими материалами от меня можно в телеграм канале: @prowebit

Читайте также  Бензиновый генератор dde g350p 3100 вт

В этом канале публикую не только статьи из этого блога, но и различные новости и мысли. Подписывайтесь ?

Случайные числа своими руками №1

В этом тексте мы рассмотрим несколько теорий и реализаций генераторов
случайных чисел. Мы так же попробуем определить оптимальный с точки зрения
размера и скорости.

ГПСЧ (PRNG) это генераторы псевдо-случайных чисел.
Никакой детерминированный алгоритм не может генерировать полностью случайные
числа, а только лишь аппроксимировать некоторые свойства случайных чисел.
Ещё Джон фон Нейман говорил, что только лишь арифметическими методами случайное
число получить невозможно. Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается. Большинство простых арифметических генераторов хотя и обладают большой
скоростью, но страдают от многих серьёзных недостатков:

  • Слишком короткий период
  • Последовательные значения не являются независимыми
  • Некоторые биты «менее случайны», чем другие
  • Неравномерное распределение
  • Обратимость

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

Этот алгоритм используется в ANSI-C. Рассмотрим его:

#define RAND_MAX 32767

unsigned long next=1;

int rand(void) <
next=next*1103515245m;
return((unsigned int)(next/65536)2768);
>

void srand(unsigned int seed) <
next=seed;
>

Где a > 0, c > 0, m > 0 — некоторые целочисленные константы. Получаемая
последовательность зависит от выбора стартового числа X0 и при разных его
значениях получаются различные последовательности случайных чисел. В то же
время, многие свойства последовательности Xk определяются выбором коэффициентов
в формуле и не зависят от выбора стартового числа. Ясно, что последовательность
чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m.
При этом длина периода равна m тогда и только тогда, когда:

1) НОД(c,m) = 1 (т.е. c и m взаимно просты);
2) a — 1 кратно p для всех простых p — делителей m;
3) a — 1 кратно 4, если m кратно 4.

При реализации выгодно выбирать m = 2e, где e — число бит в машинном слове,
поскольку это позволяет избавиться от относительно медленной операции
приведения по модулю. Младшие двоичные разряды сгенерированных таким образом случайных чисел
демонстрируют поведение, далёкое от случайного, поэтому рекомендуется
использовать только старшие разряды. Для генерации числа в диапазоне *0 — 2^32 -1* достаточно простого
умножения на мультипликатор и сложения с инкрементом. Деление по модулю
будет произведено автоматически при переполнении. Значения
мультипликатора и инкремента для этого случая получены в исследованиях
D. Knuth и H.W. Lewis.

Они рекомендуют использовать следующие коэффициенты:
a = 1664525, c = 1013904223, m = 2^32

Вот этой формулой рекомендуют пользоваться для генерации 32 битного числа.

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

; ;
; %%%%%%%%%%%%%%%%%%%% ;
; ГЕНЕРАТОР СЛУЧАЙНОГО ЧмСЛА V. 0.3 (x) 2004 СЛОН ;
; Линейный конгруэнтный генератор он не прошёл тест DIEHARD и не ;
; является криптостойким ;
; %%%%%%%%%%%%%%%%%%%% ;
; Интервал: [0..eax-1] ;
; ——————————————— ;
; Использование: call r_init ;
; mov eax,ГРАНИЦА
ИНТЕРВАЛА ;
; call brandom32 ;
; ——————————————— ;
; Результат: число в интервале [0..ГРАНИЦА
ИНТЕРВАЛА] ;
; %%%%%%%%%%%%%%%%%%%% ;

; —[Подпрограмма инициализации генератора случайных чисел]— ;

r_init:
push ebp eax edx ; Сохраняем в стэке
ebp
; eax, edx

call __delta1_ ;
__delta1_: pop ebp ; Получение дельта смещения
sub ebp,offset __delta1_ ;

db 0fh,031h ; Получаем случайное зерно
mov rand_seed,eax ;

pop edx eax ebp ; Восстанавливаем
edx
; eax, ebp

ret ; Возврат из подпрограммы

; —[Подпрограмма генерации случаного
числа в диапазоне]— ;

brandom32: ; Эта подпрограмма
; возвращает случайное число
; в диапазоне 0..eax-1

push edx ecx ebp ; Сохраняем в стэке
edx
; ecx, ebp

call __delta2_ ;
__delta2_: pop ebp ; Получение дельта смещения
sub ebp,offset __delta2_ ;

imul eax,eax,100 ; Умножаем eax на 100
push eax ; и сохраняем eax в стэке

call random32 ; Вызываем подпрограмму
; генерации случайного числа
xor edx,edx ; Обнуляем edx
pop ecx ; Восстанавливаем значение
; из стэка в ecx
div ecx ; Делим eax на ecx
xchg eax,edx ; Помещаем остаток в eax
xor edx,edx ; Обнуляем edx
push 100 ; Помещаем в ecx — 100
pop ecx ;
div ecx ; Делим eax на ecx
pop ebp ecx edx ; Восстанавливаем ebp,
ecx,
; edx
ret ; Возврат из подпрограммы

; —[Подпрограмма генерации случайного числа]— ;

random32:
push ebp

call
__delta3_ ;
__delta3_: pop ebp ; Получение дельта смещения
sub ebp,offset __delta3_ ;

mov eax,12345678h ;
rand_seed= dword ptr $-4 ;
imul eax,00019660Dh ;
add eax,03C6EF35Fh ; Математические операции
mov [ebp+rand_seed],eax ; для получения случайного
shr eax,16 ; числа
imul eax,[esp+4] ;

retn ; Возврат из подпрограммы

Метод Фибоначчи с запаздываниями (Lagged Fibonacci generator) — один из методов,
который используется для генерации псевдослучайных чисел.

Особенности распределения случайных чисел, выдаваемых линейным конгруэнтным
алгоритмом, делает невозможным их использование в статистических алгоритмах,
требующих высокого разрешения. Это происходит из-за малого периода и их
предсказуемости. Поэтому линейный
конгруэнтный метод практически не используется ни в статистике, ни в криптографии. Обычно вместо него используют
либо фибоначиевые алгоритмы (в английской литературе «Subtract-with-borrow
Generators» (SWBG)), либо «Linear feedback shift registers».

Так же широкое распространение получил «Mersenne twister»,
разработанный в 1997 году Мацумото и Нишимурой. Выигрывает у других ГПСЧ
громадным периодом (2^19937-1) и быстрой генерацией случайных чисел.
Недостатком данного алгоритма является то, что существует возможность
охарактеризовать выдаваемую последовательность, как не случайную.
Именно по этой причине данный алгоритм не применим в криптографии.
Агнер Фог разработал библиотеку реализующую Mersenne twister на ассемблере.
Его домашняя страница находится по адресу: http://www.agner.org

До недавнего времени, оптимальным вариантом генерации псевдо случайных чисел
был алгоритм Джорджа Марсаглии, который использует метод умножения с переносом.
Называется алгоритм — «Marsaglia-Multicarry».
Данный алгоритм достаточно быстрый и имеет различные периоды начиная с
2^60. Для его использования данного алгоритма на языке программирования
С достаточно вставить эту функцию в начале программы:

unsigned long mwc()
<
static unsigned long x 3456789,
y=362436069,
z=77465321,
c=13579;
unsigned long long t;
tС6905990LL*x+c;
x=y;
y=z;
c=(t>>32);
return z=(t&0xffffffff);
>

После этого используйте MWC() для генерации целого 32 битного числа.
Данная функция имеет период где-то 2^125. Она с лёгкостью прошла тесты DIEHARD
и единственным её недостатком является использование умножения,
которое значительно влияет на скорость работы данного ГПСЧ.

Вот её реализация на ассемблере:

; ;
; %%%%%%%%%%%%%%%%%%%% ;
; ГЕНЕРАТОР СЛУЧАЙНОГО ЧмСЛА V. 0.41 (x) 2005 СЛОН ;
; %%%%%%%%%%%%%%%%%%%% ;
; Интервал: [0..eax-1] ;
; ——————————————— ;
; Используется алгоритм ГПСЧ Джорджа Марсаглии — «Multiply-With-Carry(MWC)»
;
; Данный алгоритм прошёл тест DIEHARD его период 2^125
;
; ——————————————— ;
; Использование: call r_init ;
; mov eax, ГРАНИЦА
ИНТЕРВАЛА ;
; call brandom32 ;
; ——————————————— ;
; Результат: число в интервале [0..ГРАНИЦА
ИНТЕРВАЛА] ;
; %%%%%%%%%%%%%%%%%%%% ;

; —[Подпрограмма инициализации генератора случайных чисел]— ;

r_init:
push ebp eax edx ; Сохраняем в стэке
ebp, eax, edx

call __delta1_ ;
__delta1_: pop ebp ; Получение дельта смещения
sub ebp,offset __delta1_ ;

db 0fh,031h ; Получаем случайное зерно
mov [ebp+x],eax ;

pop edx eax ebp ; Восстанавливаем edx,eax,ebp

ret ; Возврат из подпрограммы

; —[Подпрограмма генерации случаного чмсла в диапазоне]— ;

brandom32: ; Эта подпрограмма
; возвращает
случайное число
; в диапазоне 0..eax-1

push edx ecx ebp ; Сохраняем в стэке
edx, ecx, ebp

call __delta2_ ;
__delta2_: pop ebp ; Получение дельта смещения
sub ebp,offset __delta2_ ;

imul eax,eax,100 ; Умножаем eax на 100
push eax ; и сохраняем eax в стэке

call random32 ; В ызываем подпрограмму
; генерации случайного числа
xor edx,edx ; Обнуляем edx
pop ecx ; Восстанавливаем значение
; из стэка в ecx
div ecx ; Делим eax на ecx
xchg eax,edx ; Помещаем остаток в eax
xor edx,edx ; Обнуляем edx
push 100 ; Помещаем в ecx — 100
pop ecx ;
div ecx ; Делим eax на ecx
pop ebp ecx edx ; Восстанавливаем
ebp, ecx, edx,
ret ; Возврат из подпрограммы

; —[Подпрограмма генерации случайного числа]— ;

random32:
push edx ecx ;
push ebp ; Сохраняем регистры в стэке

call __delta3_ ;
__delta3_: pop ebp ; Получение дельта смещения
sub ebp,offset __delta3_ ;

mov eax,12345678 ;
x = dword ptr $-4 ;
shl eax,0bh
xor eax,[ebp+x]
mov edx,362436069
y = dword ptr $-4
mov [ebp+x],edx
mov ecx,521288629
z = dword ptr $-4
mov [ebp+y],ecx
mov ebx,88675123
w = dword ptr $-4
mov [ebp+z],ebx
mov edx,[ebp+w]
shr edx,13h
xor edx,[ebp+w]
xor edx,eax
shr eax,08h
xor edx,eax
mov [ebp+w],edx
mov eax,edx

Поточные шифры и генераторы псевдослучайных чисел. Часть 1

Широкое распространение получил алгоритм генерации псевдослучайных чисел, называемый алгоритмом BBS (от фамилий авторов — L. Blum, M. Blum, M. Shub) или генератором с квадратичным остатком. Для целей криптографии этот метод предложен в 1986 году.

Он заключается в следующем. Вначале выбираются два больших простых 1 Целое положительное число большее единицы называется простым, если оно не делится ни на какое другое число, кроме самого себя и единицы. Подробнее о простых числах см. в «Основные положения теории чисел, используемые в криптографии с открытым ключом» . числа p и q . Числа p и q должны быть оба сравнимы с 3 по модулю 4, то есть при делении p и q на 4 должен получаться одинаковый остаток 3. Далее вычисляется число M = p* q , называемое целым числом Блюма. Затем выбирается другое случайное целое число х , взаимно простое (то есть не имеющее общих делителей, кроме единицы) с М . Вычисляем х0= х 2 mod M . х называется стартовым числом генератора.

Читайте также  Ацетиленовый генератор из огнетушителя

На каждом n-м шаге работы генератора вычисляется хn+1= хn 2 mod M . Результатом n-го шага является один (обычно младший) бит числа хn+1 . Иногда в качестве результата принимают бит чётности, то есть количество единиц в двоичном представлении элемента. Если количество единиц в записи числа четное – бит четности принимается равным 0 , нечетное – бит четности принимается равным 1 .

Например, пусть p = 11, q = 19 (убеждаемся, что 11 mod 4 = 3, 19 mod 4 = 3 ). Тогда M = p* q = 11*19=209 . Выберем х , взаимно простое с М : пусть х = 3 . Вычислим стартовое число генератора х :

Вычислим первые десять чисел хi по алгоритму BBS . В качестве случайных бит будем брать младший бит в двоичной записи числа хi :

х1=9 2 mod 209= 81 mod 209= 81 младший бит: 1
х2=81 2 mod 209= 6561 mod 209= 82 младший бит:
х3=82 2 mod 209= 6724 mod 209= 36 младший бит:
х4=36 2 mod 209= 1296 mod 209= 42 младший бит:
х5=42 2 mod 209= 1764 mod 209= 92 младший бит:
х6=92 2 mod 209= 8464 mod 209= 104 младший бит:
х7=104 2 mod 209= 10816 mod 209= 157 младший бит: 1
х8=157 2 mod 209= 24649 mod 209= 196 младший бит:
х9=196 2 mod 209= 38416 mod 209= 169 младший бит: 1
х10=169 2 mod 209= 28561 mod 209= 137 младший бит: 1

Самым интересным для практических целей свойством этого метода является то, что для получения n-го числа последовательности не нужно вычислять все предыдущие n чисел хi . Оказывается хn можно сразу получить по формуле

x_n=x_0^<2^n mod ((p-1)(q-1)>mod : M» /></p>
<p>Например, вычислим х<sub>10</sub> сразу из х<sub></sub> :</p>
<p><img src=

Как компьютер генерирует случайные числа

Что такое случайность в компьютере? Как происходит генерация случайных чисел? В этой статье мы постарались дать простые ответы на эти вопросы.

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

Определение того, что именно является случайностью, может быть довольно сложной задачей. Существуют тесты (например, колмогоровская сложность), которые могут дать вам точное значение того, насколько случайна та или иная последовательность. Но мы не будем заморачиваться, а просто попробуем создать последовательность чисел, которые будут казаться несвязанными между собой.

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

Создание случайных чисел из семени

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

Давайте поэкспериментируем с этой идеей и посмотрим, куда она нас приведёт.

Функция искажения будет принимать одно значение, а возвращать другое. Назовём её R.

Начнём с того, что R — это простая функция, которая всего лишь прибавляет единицу.

Если значение нашего семени 1, то R создаст ряд 1, 2, 3, 4, . Выглядит совсем не случайно, но мы дойдём до этого. Пусть теперь R добавляет константу вместо 1.

Если с равняется, например, 7, то мы получим ряд 1, 8, 15, 22, . Всё ещё не то. Очевидно, что мы упускаем то, что числа не должны только увеличиваться, они должны быть разбросаны по какому-то диапазону. Нам нужно, чтобы наша последовательность возвращалась в начало — круг из чисел!

Числовой круг

Посмотрим на циферблат часов: наш ряд начинается с 1 и идёт по кругу до 12. Но поскольку мы работаем с компьютером, пусть вместо 12 будет 0.

number circle

Теперь начиная с 1 снова будем прибавлять 7. Прогресс! Мы видим, что после 12 наш ряд начинает повторяться, независимо от того, с какого числа начать.

Здесь мы получаем очень важно свойство: если наш цикл состоит из n элементов, то максимальное число элементов, которые мы можем получить перед тем, как они начнут повторяться это n.

Теперь давайте переделаем функцию R так, чтобы она соответствовала нашей логике. Ограничить длину цикла можно с помощью оператора модуля или оператора остатка от деления.

На этом этапе вы можете заметить, что некоторые числа не подходят для c. Если c = 4, и мы начали с 1, наша последовательность была бы 1, 5, 9, 1, 5, 9, 1, 5, 9, . что нам конечно же не подходит, потому что эта последовательность абсолютно не случайная. Становится понятно, что числа, которые мы выбираем для длины цикла и длины прыжка должны быть связаны особым образом.

Если вы попробуете несколько разных значений, то сможете увидеть одно свойство: m и с должны быть взаимно простыми.

До сих пор мы делали «прыжки» за счёт добавления, но что если использовать умножение? Умножим х на константу a.

Свойства, которым должно подчиняться а, чтобы образовался полный цикл, немного более специфичны. Чтобы создать верный цикл:

  1. (а — 1) должно делиться на все простые множители m
  2. (а — 1) должно делиться на 4, если m делится на 4

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

Выбор семени

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

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

Конечный результат

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

Где начальное значение х — это семя, а — множитель, с — константа, m — оператор остатка от деления.

То, что мы сделали, называется линейным конгруэнтным методом. Он очень часто используется, потому что он прост в реализации и вычисления выполняются быстро.

В разных языках программирования реализация линейного конгруэнтного метода отличается, то есть меняются значения констант. Например, функция случайных чисел в libc (стандартная библиотека С для Linux) использует m = 2 ^ 32, a = 1664525 и c = 1013904223. Такие компиляторы, как gcc, обычно используют эти значения.

Заключительные замечания

Существуют и другие алгоритмы генерации случайных чисел, но линейный конгруэнтный метод считается классическим и лёгким для понимания. Если вы хотите глубже изучить данную тему, то обратите внимание на книгу Random Numbers Generators, в которой приведены элегантные доказательства линейного конгруэнтного метода.

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

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: