- PVSM.RU - https://www.pvsm.ru -
В английском есть такая аббревиатура — TIFU. Привести здесь её точное значение мы не можем, но вы без труда найдёте его в Сети. А после «литературной обработки» TIFU можно перевести как «сегодня я всё испортил». В контексте этого поста данная фраза относится к использованию функции Math.random() в JavaScript-движке V8. Хотя случилось это не сегодня, а пару лет назад. Да и дров я наломал не по своей вине, корень зла таится в самой этой функции.
«Многие генераторы случайных чисел, используемые сегодня, работают не слишком хорошо. Разработчики обычно стараются не вникать, как устроены такие подпрограммы. И часто бывает так, что какой-то старый, неудовлетворительно работающий метод раз за разом слепо перенимается многими программистами, которые зачастую просто не знают о присущих ему недостатках.»
Дональд Кнут, «Искусство программирования [1]», том 2.
Надеюсь, что к концу этого поста вы согласитесь с двумя утверждениями:
Хочу подчеркнуть, что сам движок V8 — замечательный продукт и его создатели очень талантливы. Я ни в коей мере не обвиняю их. Просто эта ситуация иллюстрирует, насколько сильно влияют на процесс разработки даже небольшие нюансы.
Работа проекта Betable [3] зависит от случайных чисел. Помимо прочего, с их помощью генерируются идентификаторы. Поскольку архитектура представляет собой систему распределённых микросервисов, то реализовать случайные идентификаторы было легче, чем последовательные. К примеру, при каждом запросе API генерируются случайные идентификаторы запроса. Они помещаются в подзапросы в заголовках, логируются и используются для сравнения и корреляции всех происходящих событий во всех сервисах, в качестве результата одного-единственного запроса. Ничего сложного в генерировании случайных идентификаторов нет. Требование одно:
Вероятность двукратного генерирования одного и того же идентификатора — возникновения коллизии — должна быть крайне мала. На вероятность возникновения коллизии влияют два фактора:
В идеале нам нужно большое пространство, из которого случайно выбираются равномерно распределённые идентификаторы (раз уж мы предполагаем, что любой «случайный» процесс использует равномерное распределение).
Мы посчитали вероятность коллизии из парадокса дней рождений [4] и приняли, что размер идентификатора запроса будет длиной в 22 символа, выбранных из словаря, содержащего 64 буквы. Например, EB5iGydiUL0h4bRu1ZyRIi или HV2ZKGVJJklN0eH35IgNaB. Поскольку каждый символ идентификатора может принимать одно из 64 значений, то наше идентификационное пространство имеет размер 6422 ≈ 2132. При таком размере пространства, если идентификаторы генерируются случайным образом со скоростью 1 млн в секунду, то вероятность возникновения коллизии в течение 300 лет будет составлять 1 к 6 млрд.
Хорошо, пространство получилось достаточно большим. Как нам осуществлять случайное генерирование? Напрашивается ответ: с помощью приличного псевдослучайного генератора (PRNG), который обычно можно найти во многих стандартных библиотеках. На верхнем уровне нашего стека находится сервис Node.js, а тот, в свою очередь, использует движок V8, разработанный Google для Chrome. Все совместимые реализации ECMAScript (JavaScript) должны использовать Math.random(), который без каких-либо аргументов возвращает случайное число от 0 до 1. На основе последовательности этих чисел от 0 до 1 нужно сгенерировать случайное слово, состоящее из 64 символов алфавита. Это довольно распространённая задача, для которой выработано стандартное решение:
var ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_';
random_base64 = function random_base64(length) {
var str = "";
for (var i=0; i < length; ++i) {
var rand = Math.floor(Math.random() * ALPHABET.length);
str += ALPHABET.substring(rand, rand+1);
}
return str;
}
Ссылка [5].
Не надо критиковать этот код, с ним всё в порядке, он делает именно то, что должен. Идём дальше. Разработали процедуру генерирования случайных идентификаторов с чрезвычайно низкой вероятностью возникновения коллизии. Тестируем, коммитим, пушим, тестируем, развёртываем. Вышеприведённый пример попал в production, и мы забыли о нём. Но однажды пришло письмо от одного коллеги, в котором сообщалось, что случилось невероятное:
«Каждый, кто допускает использование арифметических методов для генерирования случайных чисел, совершает грех». Джон фон Нейман говорил об очевидном: утверждение, что детерминистические методы (например, арифметические) не могут генерировать случайные числа, является тавтологией. Так что же такое PRNG?
Давайте рассмотрим простенький PRNG [6] и результаты его работы:
Эта иллюстрация поясняет мысль фон Неймана: очевидно, что сгенерированная последовательность чисел не является случайной. Для многих задач этого вполне достаточно. Но нам нужен алгоритм, генерирующий числа, которые кажутся случайными. Технически они должны казаться независимыми и одинаково распределёнными случайными переменными, равномерно распределёнными по всему диапазону генератора. Другими словами, нам нужно безопасно притвориться, что наши псевдослучайные числа являются истинно случайными.
Если результат работы генератора очень трудно отличить от истинно случайной последовательности, то его называют высококачественным генератором. В противном случае — низкокачественным. По большей части качество определяется эмпирически, путём прогона статистических тестов на уровень случайности. Например, оценивается количество нулей и единиц, вычисляется число коллизий, применяется метод Монте-Карло для вычисления π и т. д. Другой, более прагматичный метод оценки качества PRNG заключается в анализе его работы на практике и сравнении с истинно случайными числами.
Помимо неслучайности результата, рассматриваемый нами простой алгоритм демонстрирует и другие важные особенности, свойственные всем PRNG. Если долго генерировать числа, то рано или поздно начнёт повторяться одна и та же последовательность. Это свойство называется периодичностью, и ею «страдают» все PRNG.
Период, или длина цикла, — это длина последовательности чисел, создаваемых генератором до первого повторения.
Можно рассматривать PRNG как сильно сжатую шифровальную книгу, содержащую последовательность чисел. Какой-нибудь шпион мог бы использовать его в качестве одноразового блокнота. Начальной позицией в этой «книге» является seed(). Постепенно вы дойдёте до её конца и вернётесь к началу, завершив цикл.
Большая длина цикла не гарантирует высокое качество, но весьма ему способствует. Часто он гарантируется каким-то математическим доказательством. Даже когда мы не можем точно вычислить длину цикла, нам вполне по силам определить его верхнюю границу. Поскольку следующее состояние PRNG и его результат являются детерминистическими функциями текущего состояния, то длина цикла не может быть больше количества возможных состояний. Для достижения максимальной длины генератор должен пройти через все возможные состояния, прежде чем вернуться в текущее.
Если состояние PRNG описывается как k-бит, то длина цикла ≤ 2k. Если она действительно достигает этого значения, то такой генератор называют генератором полного цикла. В хороших PRNG длина цикла близка к этой верхней границе. В противном случае вы будете зря тратить память.
Давайте теперь проанализируем количество уникальных случайных значений, генерируемых PRNG с помощью некой детерминистической трансформации выходных данных. Допустим, нам надо сгенерировать три случайных числа от 0 до 15, вроде 2, 13, 4 или 5, 12, 15. У нас может быть 163 = 4096 таких тройных комбинаций, но рассматриваемый нами простой генератор может выдать лишь 16 комбинаций:
Так мы приходим к ещё одному свойству всех PRNG: количество уникальных значений, которые могут быть сгенерированы из псевдослучайной последовательности, ограничивается длиной цикла последовательности.
Неважно, какие значения мы генерируем в данном случае. Их может быть 16 комбинаций из четырёх значений (или любой другой длины), 16 уникальных матричных массивов и т. д. Не более 16 уникальных значений любого типа.
Вспомните наш алгоритм для генерирования случайных идентификаторов, состоящих из 22 символов, берущихся из 64-символьного словаря. Получается, что мы генерируем комбинации из 22 чисел от 0 до 63. И здесь мы сталкиваемся с той же проблемой: количество возможных уникальных идентификаторов ограничено размером внутреннего состояния PRNG и длиной его цикла.
Вернёмся к нашим баранам. Получив письмо о возникновении коллизии, мы быстро пересмотрели наши математические выкладки по парадоксу дней рождений и проверили код. Ничего криминального не обнаружили, значит, проблема лежит глубже. Начали разбираться.
Вот что говорится о Math.random() в спецификации ECMAScript [7]:
Возвращает положительное числовое значение, больше либо равное 0, но меньше 1, выбранное случайно или псевдослучайно с приблизительно равномерным распределением в этом диапазоне, с использованием алгоритма или стратегии, зависящих от конкретной реализации.
Спецификация оставляет желать лучшего. Во-первых, тут ничего не сказано о точности. Поскольку в ECMAScript используются числа с плавающей запятой двойной точности IEEE 754 binary64, то мы можем ожидать точность на уровне 53 бит (т. е. случайные значения принимают вид x/253, где x = 0…253 – 1). Движок SpiderMonkey от Mozilla придерживается того же мнения [8], но это не так. Как будет показано ниже, точность Math.random() в V8 составляет всего 32 бита (значения принимают вид x/232, где x = 0…232 – 1). Впрочем, это не важно, поскольку нам нужно шесть бит для генерирования случайных букв из нашего словаря.
А вот что для нас оказалось действительно важно, так это то, что спецификация не определяет конкретный алгоритм. Нет никаких требований к минимальной длине цикла, так что прощай, качество: распределение должно быть лишь «приблизительно равномерным». Значит, чтобы найти причину коллизии, нужно проанализировать конкретный алгоритм, используемый V8. В документации мы ничего не нашли, так что пришлось обращаться к исходному коду.
«Мне пришлось смириться с вихрем Мерсенна [9], потому что его используют все подряд (Python, Ruby и т. д.)». Эта краткая характеристика Дина Мак-Нами [10] является единственным содержательным отзывом на анализ кода [11] PRNG в V8, когда он был впервые закоммичен [12] 15 июня 2009 года.
За прошедшие шесть лет код PRNG в V8 переделывался и рихтовался. Раньше это был нативный код [13], а теперь он находится в пользовательском пространстве [14]. Но алгоритм остался без изменений. Текущая реализация использует внутренний API и довольно запутанна, поэтому рассмотрим более читабельную реализацию того же алгоритма:
var MAX_RAND = Math.pow(2, 32);
var state = [seed(), seed()];
var mwc1616 = function mwc1616() {
var r0 = (18030 * (state[0] & 0xFFFF)) + (state[0] >>> 16) | 0;
var r1 = (36969 * (state[1] & 0xFFFF)) + (state[1] >>> 16) | 0;
state = [r0, r1];
var x = ((r0 << 16) + (r1 & 0xFFFF)) | 0;
if (x < 0) {
x = x + MAX_RAND;
}
return x / MAX_RAND;
}
Ссылка. [15]
Выглядит малопонятно, будем разбираться.
Есть одна подсказка. В старых версиях V8 был комментарий: «генератор случайных чисел использует алгоритм MWC Джорджа Марсальи (George Marsaglia)». В поисковике нашлось следующее:
Так что если вам нужен PRNG, то MWC кажется неплохим выбором.
Но реализованный в V8 алгоритм непохож на типичный MWC. Вероятно, причина в том, что это не MWC, а сразу два MWC-генератора — один в строке 5, второй в строке 6, — совместно генерирующих одно случайное число в строке 9. Не стану выкладывать тут все расчёты, но каждый из этих подгенераторов имеет длину цикла примерно 230, что даёт суммарную длину генерируемой последовательности примерно 260.
Но у нас, как вы помните, 2132 возможных идентификаторов. Допустим, что соблюдается условие равномерного распределения. Тогда вероятность коллизии после случайно сгенерированных 100 млн идентификаторов должна быть менее 0,4%. Но коллизии стали возникать гораздо раньше. Наверное, мы где-то ошиблись с нашим анализом. Возможно, проблема заключается в равномерном распределении — вероятно, есть какая-то дополнительная структура в генерируемой последовательности.
Давайте ещё раз посмотрим на код генерирования идентификаторов:
var ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_';
random_base64 = function random_base64(length) {
var str = "";
for (var i=0; i < length; ++i) {
var rand = Math.floor(Math.random() * ALPHABET.length);
str += ALPHABET.substring(rand, rand+1);
}
return str;
}
Ссылка [5].
Большое значение имеет метод масштабирования в шестой строке. Он рекомендован MDN [22] для масштабирования случайных чисел и используется очень широко (пример 1 [23], пример 2 [24], пример 3 [25], пример 4 [26], пример 5 [27], пример 6 [28]). Метод известен под названиями multiply-and-floor, take-from-top. Последнее название он получил потому, что нижние биты случайного числа отсекаются, а левые — верхние, top, — используются в качестве масштабированного целочисленного результата.
Примечание: если отношение выходного диапазона PRNG к масштабируемому диапазону представляет дробное число, то этот метод работает с небольшим смещением (biased). Обычно это решается с помощью выборки с отклонением [29], используемой в стандартных библиотеках других [30] языков [31].
Замечаете, в чём проблема? Два генератора довольно странно миксуются в алгоритме V8. Числа из двух потоков не объединяются по модулю 2 (xor). Вместо этого просто конкатенируются нижние 16 бит выходных данных каждого подгенератора. Похоже, проблема именно в этом. Когда мы умножим Math.random() на 64 и приведём к наименьшему (floor), то у нас останутся верхние 6 битов. Эти биты генерируются исключительно одним из двух MWC-подгенераторов.
Красным выделены биты от PRNG № 1, синим — от PRNG № 2.
Если независимо проанализируем первый подгенератор, то увидим, что его внутреннее состояние имеет длину 32 бита. Это не генератор полного цикла, реальная длина составляет около 590 млн: 18,030 * 215 – 1, подробности вычислений можно узнать здесь — ссылка 1 [19], ссылка 2 [32]. То есть мы можем сгенерировать не более 590 млн уникальных идентификаторов запроса. И если бы они выбирались случайным образом, то после 30 тыс. генераций вероятность коллизии составила бы 50%.
Но будь это так, мы почти сразу же начали бы замечать коллизии. Но мы их не замечали. Чтобы понять, почему этого не происходило, давайте вспомним пример с генерированием комбинаций из трёх чисел средствами 4-битного LCG.
В данном случае парадокс дней рождений неприменим — последовательность даже близко нельзя назвать случайной, так что мы не можем притвориться. Очевидно, что до 17-й комбинации дублей не будет. То же самое происходит и с PRNG в V8: при определённых условиях недостаток случайности снижает вероятность того, что мы увидим коллизию.
То есть детерминированность генератора сыграла нам на руку. Но так бывает не всегда. Главный вывод, который мы сделали, заключается в том, что даже в высококачественном PRNG нельзя предполагать случайность распределения, если длина цикла не будет гораздо больше, чем количество генерируемых вами значений.
Если вам нужно N случайных значений, то необходимо использовать PRNG с длиной цикла как минимум N2. Причина этого в том, что, с учётом периода PRNG, избыточная равномерность может снизить производительность в некоторых важных статистических тестах (в особенности в тестах на наличие коллизий). Чтобы этого не происходило, размер выборки N должен быть пропорционален квадратному корню из длины периода. Подробнее об этом можно почитать на странице 22 замечательной работы [21] Пьера Лекюйе, в главе, посвящённой генераторам случайных чисел.
В случаях, подобных нашему, когда пытаются генерировать уникальные значения с помощью нескольких независимых последовательностей от одного генератора, беспокоятся не столько о случайности, сколько о том, чтобы последовательности не совпадали. Допустим, у нас есть N последовательностей с длиной L от генератора с периодом P. Тогда вероятность совпадения будет равна
Для достаточно больших значений P вероятность будет примерно равна LN2/P (подробности: ссылка 1 [33], ссылка 2 [34]). Значит, нам нужен цикл большой длины, иначе мы будем ошибочно притворяться, что наша последовательность является случайной.
Короче, если вы используете Math.random() в V8 и вам нужна достаточно качественная последовательность случайных чисел, то не используйте более 24 тыс. чисел. А если генерируете в несколько мощных потоков и вам нужно избегать совпадений, то вообще забудьте о Math.random().
«Генератор MWC конкатенирует два 16-битных multiply-with-carry-генератора […] обладает периодом 260 и, похоже, проходит все тесты на случайность. Любимый отдельный генератор — быстрее, чем содержащий его KISS». Это отрывок из описания алгоритма MWC1616, лежащего в основе Math.random() в V8. Судя по словам Марсальи, удовлетворяет большинству основных критериев, по которым выбирают PRNG.
MWC1616 был представлен [35] в 1997 году в качестве простого основного генератора. Фраза «похоже, проходит все тесты на случайность» выдаёт эмпиричность методологии Марсальи. Он, кажется, доверял алгоритму, раз тот прошёл тесты Diehard. К сожалению, те тесты, что он использовал в конце 1990-х, были недостаточно хороши, по крайней мере исходя из современных стандартов. Если прогнать MWC1616 через более современный тестировочный фреймворк вроде TestU01 [36], то результат будет катастрофическим [37]. Даже генератор MINSTD [38] показывает результат лучше, а он устарел ещё в 1990-х. Вероятно, тесты Diehard просто не были достаточно детализированными, поэтому Марсалья сделал такой вывод.
// January 12, 1999 / V8 PRNG: ((r0 << 16) + (r1 ^ 0xFFFF)) % 2^32
var x = ((r0 << 16) + (r1 & 0xFFFF)) | 0;
// January 20, 1999: (r0 << 16) + r1) % 2^32
var x = ((r0 << 16) + r1) | 0;
Ссылка [39].
Насколько мне известно, у процедуры конкатенации двух подмножеств сгенерированных битов, выполняемой в MWC1616, нет никакой математической базы. Обычно биты от подгенераторов объединяются с помощью арифметических операций по модулю (например, xor). Похоже, Марсалья озаботился отсутствием математической базы вскоре после опубликования своего алгоритма в качестве компонента одной из версий генератора KISS [40]. 12 января 1999 года вышла версия MWC1616, использовавшаяся в V8. А уже 20 января Марсалья опубликовал другую версию [41] своего алгоритма. В ней верхние биты второго генератора не отбрасываются, потоки смешиваются точнее.
Обе версии алгоритма появились на разных ресурсах, что внесло путаницу. Поздняя (улучшенная) версия, названная MWC with Base b = 216, опубликована на Numerical Recipes [42] под заголовком «Когда у вас только 32-битные вычисления». И вместо внедрения одного из алгоритмов предлагалось «использовать компилятор получше!». Довольно унылый совет по отношению к алгоритму, который лучше используемого в V8. По необъяснимой причине версия от 20 января приводится в Википедии в качестве примера [43] вычислительного метода для генерирования случайных чисел. Более старая версия от 12 января дважды включалась в TestU01 [44], сначала под названием MWC1616, а потом MWC97R. Также этот алгоритм применяется в качестве одного из генераторов в языке R [45].
В общем, MWC используется довольно широко. И надеюсь, эта статья послужит предостережением для многих разработчиков, став развитием и подтверждением наблюдений Кнута:
Есть немало более полезных вариантов. Давайте рассмотрим парочку.
Итак, нам надо было чем-то быстро заменить Math.random(). Для JavaScript существует множество других PRNG, но у нас было два условия:
К счастью, в стандартной библиотеке Node.js есть другой генератор, удовлетворяющий нашим требованиям: crypto.randomBytes() [46], криптографически безопасный PRNG (CSPRNG), вызывающий RAND_bytes [47], используемый в OpenSSL. Согласно документам [48], тот выдаёт случайное число с помощью хэша SHA-1 с внутренним состоянием на 8184 бита, который регулярно перерандомизируется (reseed) из разных энтропических источников. В веб-браузере то же самое должен делать crypto.getRandomValues() [49].
У этого решения есть три недостатка:
Однако есть и преимущества:
Всё ещё приходится делать некие допущения, но они хотя бы прагматичны и базируются на каких-то доказательствах. Если вы не уверены в качестве своих некриптографических альтернатив, то лучше всего пользоваться CSPRNG. По крайней мере, до тех пор, пока вам не понадобятся детерминистическое рандомизирование или строгие доказательства качества генератора. Если вы не доверяете CSPRNG из своей стандартной библиотеки (а ради надёжности криптографии этого и нельзя делать), то можете воспользоваться urandom [50], который управляется ядром (в Linux используется схема, аналогичная OpenSSl, а в OS X — генератор Yarrow [51]).
Я не знаю, какова длина цикла в crypto.randomBytes(). Насколько мне известно, у этой проблемы не существует решения в замкнутой форме. Могу сказать лишь, что при большом пространстве состояния и длительном потоке входящей энтропии алгоритм должен быть достаточно безопасен. Раз уж вы доверяете OpenSSL генерирование пар публичных/личных ключей, то какой смысл беспокоиться по этому поводу? После того как мы заменили Math.random() на crypto.randomBytes(), проблема коллизий исчезла.
На самом деле Chrome мог бы заставить Math.random() вызвать тот же CSPRNG, который используется для crypto.randomBytes(). Судя по всему, WebKit именно это и делает [52]. В любом случае есть немало других быстрых и высококачественных некриптографических альтернатив.
Я хочу доказать вам, что использовать Math.random() в V8 нельзя, этот инструмент необходимо заменить. Мы уже обсудили наличие очевидных структурных паттернов в выходных данных, проваленные практические тесты и низкую производительность в реальных проектах. Если вам всё ещё мало доказательств, то взгляните на это:
Сверху — шум на основе случайных данных из Safari, снизу — из V8. Картинки сгенерированы в браузере с помощью этого кода [53]:
Вычисление числа π с помощью алгоритма Монте-Карло, 1010 итераций. Код [54].
Надеюсь, вы теперь согласитесь, что с Math.random() пора что-то делать. Вопрос — что именно. Корректировка одной строки позволит улучшить объединение битов, но я вообще не вижу смысла держаться за MWC1616. Есть варианты получше.
Я не собираюсь устраивать здесь детальное сравнение множества существующих методов генерирования псевдослучайных чисел. Но хотя бы формализую критерии, которым должны удовлетворять подходящие генераторы:
Существует много PRNG, удовлетворяющих этим требованиям или перекрывающих их. Генераторы xorshift [58] (тоже разработанные Марсальей) имеют высокую производительность и показывают отличные результаты на статистических тестах. Один из вариантов, под названием xorgens4096, был реализован на JavaScript [59]. Он обладает пространством состояний 4096 бит, длиной цикла около 24096 и работает в Chrome на моей машине быстрее [60], чем MWC1616. Кроме того, не проваливает систематически BigCrush.
Недавно было показано [61], что умножение выходных данных xorshift-генератора на константу является достаточно нелинейной трансформацией, поэтому генератор не пройдёт BigCrush. Этот класс генераторов называется xorshift*. Они работают очень быстро, эффективно используют память и легкореализуемы [62]. Генератор xorshift1024* удовлетворяет всем нашим требованиям, некоторым даже с избытком. Xorshift64* потребляет столько же памяти, у него длиннее цикл, работает быстрее MWC1616. Для нового семейства гибридных линейно-нелинейных генераторов — PCG [63] — заявлены такие же характеристики производительности и качества.
В общем, есть из чего выбрать. Безопаснее всего, наверное, стандартный вихрь Мерсенна. Его наиболее популярным вариантом является MT19937, представленный [64] в конце 1990-х. С тех пор он стал стандартным генератором в десятках продуктов [65]. Вещь неидеальная, но зато хорошо протестированная и тщательно проанализированная. С ним легко разобраться, неплохо ведёт себя в практических тестах. Длина цикла составляет аж 219937 – 1, у него внушительные 2 Кб пространства состояний и его критикуют за большое потребление памяти и не слишком высокую производительность. Есть и реализация на JavaScript [66]. Я не сравнивал его производительность с Math.random() в Chrome на своём компьютере.
Короче, я полностью согласен с комментарием Дина Мак-Нами шестилетней давности и рекомендую использовать вихрь Мерсенна. Его могут без опаски применять те разработчики, которые не слишком хорошо представляют себе устройство генераторов псевдослучайных чисел. Если хотите — используйте более экзотические альтернативы. Но только избавьтесь от MWC1616, прошу вас!
Это был длинный пост. Давайте подведём краткие итоги:
Напоследок замечу, что используемый Mozilla LCG-генератор [67] из Java-пакета util.Random не сильно лучше, чем MWC1616. Так что есть смысл обновить генератор и в SpiderMonkey.
В то же время браузеры остаются тёмным и опасным местом. Берегите себя!
Автор: Mail.Ru Group
Источник [68]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/javascript/107598
Ссылки в тексте:
[1] Искусство программирования: https://ru.wikipedia.org/wiki/%D0%98%D1%81%D0%BA%D1%83%D1%81%D1%81%D1%82%D0%B2%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F
[2] криптографически стойкие генераторы псевдослучайных чисел: https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8_%D1%81%D1%82%D0%BE%D0%B9%D0%BA%D0%B8%D0%B9_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D0%BF%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB
[3] Betable: https://eng.betable.com/
[4] парадокса дней рождений: https://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%BE%D0%BA%D1%81_%D0%B4%D0%BD%D0%B5%D0%B9_%D1%80%D0%BE%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D1%8F
[5] Ссылка: https://gist.github.com/mmalone/153e9c1872cd2927ca66#file-random_base64-js
[6] простенький PRNG: https://gist.github.com/mmalone/6ef9fabe1a7540ae89e8
[7] спецификации ECMAScript: http://www.ecma-international.org/ecma-262/6.0/#sec-math.random
[8] того же мнения: http://mxr.mozilla.org/mozilla-central/source/js/src/jsmath.h#133
[9] вихрем Мерсенна: https://ru.wikipedia.org/wiki/%D0%92%D0%B8%D1%85%D1%80%D1%8C_%D0%9C%D0%B5%D1%80%D1%81%D0%B5%D0%BD%D0%BD%D0%B0
[10] Дина Мак-Нами: http://www.deanmcnamee.com/about
[11] анализ кода: https://codereview.chromium.org/126113
[12] впервые закоммичен: https://github.com/v8/v8/commit/aa176ce815355f5c7e9d4b91e8f5627f12e7109b
[13] нативный код: https://github.com/v8/v8/blob/e40cde49b52ad795212699ac167db467993af0e0/src/v8.cc#L148-L159
[14] пользовательском пространстве: https://github.com/v8/v8/blob/b0e4dce6091a8777bda80d962df76525dc6c5ea9/src/js/math.js#L135-L144
[15] Ссылка.: https://gist.github.com/mmalone/ce523298670da66acaa1#file-mwc1616-js
[16] Джордж Марсалья: https://en.wikipedia.org/wiki/George_Marsaglia
[17] тесты Diehard: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82%D1%8B_diehard
[18] multiply-wit-carry: https://en.wikipedia.org/wiki/Multiply-with-carry
[19] разработанный Марсальей: http://digitalcommons.wayne.edu/cgi/viewcontent.cgi?article=1725&context=jmasm
[20] линейные конгруэнтные генераторы: https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BD%D0%B3%D1%80%D1%83%D1%8D%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4
[21] этого документа: http://www.iro.umontreal.ca/~lecuyer/myftp/papers/handstat.pdf
[22] рекомендован MDN: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random
[23] пример 1: https://github.com/google/closure-library/blob/master/closure/goog/math/math.js#L25-L32
[24] пример 2: https://github.com/jashkenas/underscore/blob/98d3b2199c1e3b1853aa22e62188638e67f30d2f/underscore.js#L1398
[25] пример 3: https://github.com/mbostock/d3/wiki/Math
[26] пример 4: http://stackoverflow.com/questions/4959975/generate-random-value-between-two-numbers-in-javascript
[27] пример 5: http://www.w3schools.com/jsref/jsref_random.asp
[28] пример 6: http://blog.tompawlak.org/how-to-generate-random-values-nodejs-javascript
[29] выборки с отклонением: https://gist.github.com/mmalone/d710793137ed0d6b8cb4
[30] других: https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/Random.java#L298-L311
[31] языков: https://github.com/python/cpython/blob/3.5/Lib/random.py#L241-L246
[32] ссылка 2: https://en.wikipedia.org/wiki/Multiply-with-carry#General_theory
[33] ссылка 1: http://xorshift.di.unimi.it/
[34] ссылка 2: http://www.mathpages.com/home/kmath580/kmath580.htm
[35] представлен: https://groups.google.com/forum/#!searchin/sci.stat.math/A$20random$20number$20generator$20for$20C./sci.stat.math/1kNyF8ixyqc/RHeuadKl0ocJ
[36] TestU01: http://simul.iro.umontreal.ca/testu01/tu01.html
[37] катастрофическим: https://gist.github.com/mmalone/8b43c628c39cc39aa205
[38] генератор MINSTD: https://en.wikipedia.org/wiki/Lehmer_random_number_generator#Parameters_in_common_use
[39] Ссылка: https://gist.github.com/mmalone/178e4e9484231b343a1a#file-mwc1616-versions-js
[40] генератора KISS: https://eprint.iacr.org/2011/007.pdf
[41] другую версию: https://groups.google.com/forum/#!msg/sci.math.num-analysis/yoaCpGWKEk0/UXCxgufdTesJ
[42] Numerical Recipes: http://numerical.recipes/
[43] примера: https://en.wikipedia.org/wiki/Random_number_generation#Computational_methods
[44] дважды включалась в TestU01: http://simul.iro.umontreal.ca/testu01/guideshorttestu01.pdf
[45] в языке R: https://github.com/wch/r-source/blob/66e40c3ba1d7ebb78c84694fbd5780b452b52071/src/main/RNG.c#L118-L121
[46] crypto.randomBytes(): https://nodejs.org/api/crypto.html#crypto_crypto_randombytes_size_callback
[47] RAND_bytes: https://github.com/nodejs/node/blob/7eee37257fe708ec23e8be292047320491ac8361/src/node_crypto.cc#L5107-L5108
[48] документам: https://wiki.openssl.org/index.php/Manual:Rand%283%29
[49] crypto.getRandomValues(): https://developer.mozilla.org/en-US/docs/Web/API/RandomSource/getRandomValues
[50] urandom: http://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/
[51] Yarrow: https://www.schneier.com/yarrow.html
[52] WebKit именно это и делает: http://trac.webkit.org/browser/trunk/Source/WTF/wtf/RandomNumber.cpp#L41
[53] этого кода: http://bl.ocks.org/mmalone/bf59aa2e44c44dde78ac
[54] Код: https://gist.github.com/mmalone/796d959dcf5b780106f4
[55] Dieharder: https://www.phy.duke.edu/~rgb/General/dieharder.php
[56] тесты NIST: http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html
[57] rngtest: https://www.gnu.org/software/hurd/user/tlecarrour/rng-tools.html
[58] xorshift: https://en.wikipedia.org/wiki/Xorshift
[59] реализован на JavaScript: https://github.com/davidbau/seedrandom/blob/released/lib/xor4096.js
[60] быстрее: http://jsperf.com/prng-performance/2
[61] было показано: http://vigna.di.unimi.it/ftp/papers/xorshift.pdf
[62] легкореализуемы: https://gist.github.com/mmalone/173e20becc755ebb2658
[63] PCG: http://www.pcg-random.org/
[64] представленный: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
[65] стандартным генератором в десятках продуктов: https://en.wikipedia.org/wiki/Mersenne_Twister#Adoption_in_software_systems
[66] реализация на JavaScript: https://gist.github.com/banksean/300494
[67] используемый Mozilla LCG-генератор: http://mxr.mozilla.org/mozilla-central/source/js/src/jsmath.cpp#816
[68] Источник: http://habrahabr.ru/post/274253/
Нажмите здесь для печати.