Заполнение генератора случайных чисел в Javascript - PullRequest
311 голосов
/ 06 февраля 2009

Возможно ли заполнить генератор случайных чисел (Math.random) в Javascript?

Ответы [ 13 ]

166 голосов
/ 06 февраля 2009

Нет, это не так, но довольно легко написать свой собственный генератор или, что еще лучше, использовать уже существующий. Проверьте: этот связанный вопрос .

Также см. Блог Дэвида Бау для дополнительной информации о посеве .

142 голосов
/ 10 октября 2013

ПРИМЕЧАНИЕ. Несмотря на (или, скорее, из-за) краткости и кажущейся элегантности, этот алгоритм ни в коем случае не является высококачественным с точки зрения случайности. Ищите, например, перечисленные в этот ответ для лучших результатов.

(Первоначально адаптировано из умной идеи, представленной в комментарии к другому ответу.)

var seed = 1;
function random() {
    var x = Math.sin(seed++) * 10000;
    return x - Math.floor(x);
}

Вы можете установить seed на любое число, просто избегайте нуля (или любого кратного Math.PI).

Элегантность этого решения, на мой взгляд, обусловлена ​​отсутствием каких-либо "магических" чисел (кроме 10000, которое представляет собой минимальное количество цифр, которое вы должны выбросить, чтобы избежать нечетных шаблонов - смотрите результаты со значениями 10 , 100 , 1000 ). Краткость тоже хороша.

Это немного медленнее, чем Math.random () (в 2 или 3 раза), но я считаю, что оно примерно так же быстро, как и любое другое решение, написанное на JavaScript.

64 голосов
/ 01 декабря 2017

Я реализовал ряд хороших, коротких и быстрых копируемых 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 г.

38 голосов
/ 10 октября 2013

Нет, но вот простой псевдослучайный генератор, реализация Умножение с переносом Я адаптирован из Википедия (с тех пор удалено):

var m_w = 123456789;
var m_z = 987654321;
var mask = 0xffffffff;

// Takes any integer
function seed(i) {
    m_w = (123456789 + i) & mask;
    m_z = (987654321 - i) & mask;
}

// Returns number between 0 (inclusive) and 1.0 (exclusive),
// just like Math.random().
function random()
{
    m_z = (36969 * (m_z & 65535) + (m_z >> 16)) & mask;
    m_w = (18000 * (m_w & 65535) + (m_w >> 16)) & mask;
    var result = ((m_z << 16) + (m_w & 65535)) >>> 0;
    result /= 4294967296;
    return result;
}

РЕДАКТИРОВАТЬ: исправлена ​​функция начального заполнения путем сброса m_z
РЕДАКТИРОВАТЬ 2: Серьезные недостатки реализации были исправлены

25 голосов
/ 26 апреля 2014

Алгоритм Антти Сыкэри хорош и короток. Сначала я сделал вариант, который заменил Javascript Math.random при вызове Math.seed (s), но затем Джейсон заметил, что возвращение функции будет лучше:

Math.seed = function(s) {
    return function() {
        s = Math.sin(s) * 10000; return s - Math.floor(s);
    };
};

// usage:
var random1 = Math.seed(42);
var random2 = Math.seed(random1());
Math.random = Math.seed(random2());

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

10 голосов
/ 04 марта 2017

Пожалуйста, смотрите работы Пьера Л'Экуйера, относящиеся ко времени конца 1980-х и начала 1990-х годов. Есть и другие. Создание (псевдо) генератора случайных чисел самостоятельно, если вы не являетесь экспертом, довольно опасно, потому что высока вероятность того, что результаты не будут статистически случайными или будут иметь небольшой период. Пьер (и другие) собрал несколько хороших (псевдо) генераторов случайных чисел, которые легко реализовать. Я использую один из его генераторов LFSR.

https://www.iro.umontreal.ca/~lecuyer/myftp/papers/handstat.pdf

Фил Трой

3 голосов
/ 07 декабря 2017

Многие люди, которым в наши дни нужен генератор случайных чисел в Javascript, используют модуль случайного числа Дэвида Бау .

3 голосов
/ 26 февраля 2017

Создать собственный генератор псевдослучайных данных довольно просто.

Предложение Дейва Скотезе полезно, но, как отмечают другие, оно не совсем равномерно распределено.

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

Поэтому вместо sin (x) используйте arg (exp (i * x)) / (2 * PI).

Если вам не нравится линейный порядок, смешайте его немного с xor. Фактический фактор тоже не имеет большого значения.

Для генерации n псевдослучайных чисел можно использовать код:

function psora(k, n) {
  var r = Math.PI * (k ^ n)
  return r - Math.floor(r)
}
n = 42; for(k = 0; k < n; k++) console.log(psora(k, n))

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

3 голосов
/ 04 апреля 2015

Комбинируя некоторые из предыдущих ответов, мы ищем случайную случайную функцию:

Math.seed = function(s) {
    var mask = 0xffffffff;
    var m_w  = (123456789 + s) & mask;
    var m_z  = (987654321 - s) & mask;

    return function() {
      m_z = (36969 * (m_z & 65535) + (m_z >>> 16)) & mask;
      m_w = (18000 * (m_w & 65535) + (m_w >>> 16)) & mask;

      var result = ((m_z << 16) + (m_w & 65535)) >>> 0;
      result /= 4294967296;
      return result;
    }
}

var myRandomFunction = Math.seed(1234);
var randomNumber = myRandomFunction();
0 голосов
/ 10 апреля 2019

Math.random нет, но run библиотека решает эту проблему. Он имеет почти все дистрибутивы, которые вы можете себе представить, и поддерживает генерацию случайных чисел. Пример:

ran.core.seed(0)
myDist = new ran.Dist.Uniform(0, 1)
samples = myDist.sample(1000)
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...