JavaScript генератор псевдослучайных последовательностей - PullRequest
Новая
       44

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

3 голосов
/ 25 августа 2011

Мне нужно сгенерировать детерминированную (т. Е. Повторяемую) последовательность из псевдослучайных чисел с заданным начальным числом и выбрать n-й элемент из этой последовательности.

Если случайная функция JavaScript была возможнойЯ мог бы просто сделать: 

function randomNth(seed, seq)
{
    var r;
    Math.randomSeed(seed);
    for (var i = 0; i++ < seq; i++)
    {
        r = Math.random();
    }
    return r;
}

Однако, это не так, и альтернативные посеянные PRNG выглядят немного медленными;запрашивать 250-е число будет дорого.

Я думаю, что здесь мне нужен хеш, возможно, что-то вроде md5(seed + seq) % max, но в JavaScript нет md5 (), и если я делаю это в коде, естьвозможно лучший выбор хеша.

Я бы хотел функцию где

x = randomNth(seed, seq, maxVal) // x is int && x >= 0 && x < maxVal

или, в идеале

x = randomNth(seed, seq) // x >= 0 && x < 1, same as Math.random()

Другие требования:

  • должно выполняться в файле node.js и в браузере.
  • числа должны быть статистически случайными (или достаточно близкими, так как период будет небольшим)
  • должно быть O (1) и достаточно быстродействующим

Ответы [ 4 ]

2 голосов
/ 25 августа 2011

В конце концов я использовал предложение друга (не SO).Я выбрал CRC32 (), так как он очень быстрый и дает достаточно случайные значения.

return crc32(seq + seed) % maxVal;

За восемь миллионов выдается следующее распределение для maxVal = 8:

0 999998

1 999998

2 1000007

3 1000003

4 1000001

5 1000003

6 999992

7 999998

Я также выполнил " знаменитую батарею испытаний" Hard Hard "Марсальи ", упомянутую на странице Дональда Кнута, упомянутую Гансом, результаты которого здесь: CRC32 () для случайных чисел Результаты Diehard .Короче говоря, он с треском проваливается (для такого небольшого количества тестовых данных), но все же достаточно хорош для моих нужд, когда генерирует числа в небольшом диапазоне.

2 голосов
/ 25 августа 2011

На этой странице есть несколько хороших хеш-функций int -> int, вы можете использовать одну из них. 

function hash(a)
{
    a = (a+0x7ed55d16) + (a<<12);
    a = (a^0xc761c23c) ^ (a>>19);
    a = (a+0x165667b1) + (a<<5);
    a = (a+0xd3a2646c) ^ (a<<9);
    a = (a+0xfd7046c5) + (a<<3);
    a = (a^0xb55a4f09) ^ (a>>16);
    if( a < 0 ) a = 0xffffffff + a;
    return a;
}
var seed = 26254;
var index = 250;
alert( hash( seed + index ) );
1 голос
/ 25 августа 2011
1 голос
/ 25 августа 2011

Дональд Кнут может помочь: http://www -cs-faculty.stanford.edu / ~ uno / news02.html # rng

...