Я реализовал ряд хороших, коротких и быстрых копируемых PRNG-функций в простом JavaScript. Все они могут быть засеяны и дают качественные номера.
Прежде всего, позаботьтесь о правильной инициализации ваших PRNG. Большинство генераторов ниже не имеют встроенной процедуры генерации начального числа, но принимают одно или несколько 32-битных значений в качестве начальных состояние ПРНГ. Подобные начальные числа (например, начальные числа 1 и 2) могут вызывать корреляции в более слабых PRNG, приводя к тому, что выходные данные имеют сходные свойства (такие как случайно сгенерированные уровни, являющиеся подобными). Чтобы избежать этого, рекомендуется инициализировать PRNG с хорошо распределенным начальным числом.
К счастью, хеш-функции очень хороши при генерации начальных значений для PRNG из коротких строк. Хорошая хеш-функция будет генерировать очень разные результаты, даже если две строки похожи. Вот пример, основанный на функции микширования MurmurHash3:
function xmur3(str) {
for(var i = 0, h = 1779033703 ^ str.length; i < str.length; i++)
h = Math.imul(h ^ str.charCodeAt(i), 3432918353),
h = h << 13 | h >>> 19;
return function() {
h = Math.imul(h ^ h >>> 16, 2246822507);
h = Math.imul(h ^ h >>> 13, 3266489909);
return (h ^= h >>> 16) >>> 0;
}
}
Каждый последующий вызов функции возврата создает новое «случайное» 32-битное хеш-значение, которое будет использоваться в качестве начального числа в PRNG. Вот как это можно использовать:
// Create xmur3 state:
var seed = xmur3("apples");
// Output four 32-bit hashes to provide the seed for sfc32.
var rand = sfc32(seed(), seed(), seed(), seed());
// Output one 32-bit hash to provide the seed for mulberry32.
var rand = mulberry32(seed());
// Obtain sequential random numbers like so:
rand();
rand();
Это, конечно, функциональный JS, но его можно объективизировать.
Еще одна вещь, которую стоит отметить, - это все 32-битные генераторы, что означает, что все связано 32-битными операциями, имитирующими 32-битный C-код. Это оказывается достойным компромиссом, поскольку 32-разрядные целые числа получают некоторый импульс оптимизации в современных движках JS. JS может выполнять только 32-битные побитовые операции и даже не может выполнять 64-битную математику. У JS есть ограничение в 53-битных целых числах, но даже тогда вам нужно много хитростей, чтобы эффективно их использовать. Вот почему якобы сверхбыстрый 53-разрядный генератор Alea от Baagøe на медленнее , чем эти реализации.
Вперед к товарам (генераторам).
SFC32
Этот драгоценный камень взят из набора для тестирования случайных чисел PractRand, из которого он проходит без проблем. PractRand якобы даже более строг, чем TestU01. sfc32 имеет 128-битное состояние и также очень быстр в JS (xoshiro128 ** немного быстрее, но хуже по качеству). Это, вероятно, мой PRNG выбора.
function sfc32(a, b, c, d) {
return function() {
a >>>= 0; b >>>= 0; c >>>= 0; d >>>= 0;
var t = (a + b) | 0;
a = b ^ b >>> 9;
b = c + (c << 3) | 0;
c = (c << 21 | c >>> 11);
d = d + 1 | 0;
t = t + d | 0;
c = c + t | 0;
return (t >>> 0) / 4294967296;
}
}
Mulberry32
Mulberry32 также довольно быстр и имеет хорошее качество (автор заявляет, что он прошел все тесты gjrand ). Я бы порекомендовал это, если вам просто нужен простой, но приличный PRNG.
Имеет состояние 32 бита и полный период 2 32 . Идеально, если вы хотите использовать только одно 32-разрядное целое число и не беспокоиться о проблеме дня рождения . В Mulberry32 есть 4,3 миллиарда возможных состояний по сравнению с 340 ундециллионами в sfc32 / xoshiro128 **.
function mulberry32(a) {
return function() {
var t = a += 0x6D2B79F5;
t = Math.imul(t ^ t >>> 15, t | 1);
t ^= t + Math.imul(t ^ t >>> 7, t | 61);
return ((t ^ t >>> 14) >>> 0) / 4294967296;
}
}
xoshiro128 **
По состоянию на май 2018 года xoshiro128 ** является новым членом семейства Xorshift . Он предлагает 128-битное состояние и работает очень быстро.
function xoshiro128ss(a, b, c, d) {
return function() {
var t = b << 9, r = a * 5; r = (r << 7 | r >>> 25) * 9;
c ^= a; d ^= b;
b ^= c; a ^= d; c ^= t;
d = d << 11 | d >>> 21;
return (r >>> 0) / 4294967296;
}
}
Этот PRNG является последним от Blackman / Vigna, который также написал PRNGs xorshift128 + и xoroshiro, которые использовались в Google Chrome в 2015 году. Он известен как один из немногих современных PRNG с 32-битной версией. xoroshiro64 ** также является многообещающим вариантом, но имеет только 64-битное состояние и в значительной степени заменено на xoshiro.
Авторы утверждают, что он хорошо проходит тесты на случайность ( хотя и с оговорками ). Другие исследователи отмечают, что некоторые тесты в BigCrush не проходят (особенно LinearComp и BinaryRank). Но на практике это не должно иметь значения, особенно если 32-битное значение преобразуется в число с плавающей запятой между 0-1, как эти PRNG. Однако это может вызвать проблему, если вы полагаетесь на младшие биты.
1065 * JSF *
Это JSF или «smallprng» Боба Дженкинса (2007), парня, который создал ISAAC и SpookyHash . Он хорошо работает в тестах PractRand и должен быть довольно быстрым. Предполагается, что средняя продолжительность периода составляет 2 ^ 126, но «формально не определена».
function JSF(seed) {
function jsf() {
var e = s[0] - (s[1]<<27 | s[1]>>>5);
s[0] = s[1] ^ (s[2]<<17 | s[2]>>>15),
s[1] = s[2] + s[3],
s[2] = s[3] + e, s[3] = s[0] + e;
return (s[3] >>> 0) / 4294967296; // 2^32
}
seed >>>= 0;
var s = [0xf1ea5eed, seed, seed, seed];
for(var i=0;i<20;i++) jsf();
return jsf;
}
Эта версия не требует отдельной функции заполнения. Но в результате можно посеять только 32 бита, и эта версия предварительно запускает jsf () 20 раз для разгона исходного состояния, что может быть дорогостоящим.
При необходимости можно полностью инициализировать все 128-битное состояние и удалить цикл for. Я решил оставить исходную конструкцию, потому что автор проверил длину цикла каждого возможного 32-разрядного начального числа в данной конфигурации.
LCG (он же Lehmer / Park-Miller RNG или MLCG)
Это только здесь, чтобы предоставить лучшую альтернативу опциям, упомянутым в других ответах, таких как методы Math.sin или Math.PI, которые менее согласованы или надежны на разных платформах. Эта реализация LCG является чрезвычайно быстрой , но имеет только 31-битное состояние и не проходит некоторые статистические тесты, которые ранее упомянутые генераторы прошли с плавающими цветами. Хотя это однострочный текст, что приятно:).
var LCG=s=>()=>(2**31-1&(s=Math.imul(48271,s)))/2**31;
Это минимальный стандарт ГСЧ, предложенный Парк-Миллером в 1988 и 1993 и реализованный в C ++ 11 как minstd_rand. Помните, что состояние и период только 31-битный (31 бит дает 2 миллиарда возможных состояний, 32 бита - вдвое больше). Это тот самый тип PRNG, который пытаются заменить другие.
Это будет работать, но я бы не стал его использовать, если вам действительно не нужна скорость и не нужно заботиться о качестве случайности (что в любом случае случайное?) Или если 31-битное состояние / период Размер беспокоит вас. Отлично подходит для игрового джема или демо или что-то. Кроме того, LCG страдают от начальных корреляций, поэтому лучше отбросить первый результат LCG.
Кажется, есть другие множители, которые предлагают полное 32-битное состояние. Я понятия не имею, статистически лучше или хуже, чем Парк-Миллер, но здесь они для полноты.
var LCG=s=>()=>((s=Math.imul(741103597,s))>>>0)/2**32;
var LCG=s=>()=>((s=Math.imul(1597334677,s))>>>0)/2**32;
Эти множители из: P. L'Ecuyer: таблица линейных конгруэнтных генераторов разных размеров и хорошей решетчатой структуры, 30 апреля 1997 г.