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

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

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

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

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

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

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.

Я реализовал ряд хороших, коротких и быстрых функций генератора псевдослучайных чисел (PRNG) в простом JavaScript. Все они могут быть посеяны и предоставлять качественные номера.

Прежде всего, позаботьтесь о правильной инициализации ваших PRNG. Большинство приведенных ниже генераторов не имеют встроенной процедуры генерации начальных значений (для простоты), но принимают одно или несколько 32-битных значений в качестве начального состояния PRNG. Подобные начальные числа (например, простые начальные числа 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;
    }
}

Каждый последующий вызов функции возврата из xmur3создает новый «случайный» 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();

В качестве альтернативы, просто выберите несколько фиктивных данных для заполнения начального числа и продвиньте генератор несколько раз (12-20 итераций), чтобы тщательно перемешать исходное состояние. Это часто наблюдается в ссылочных реализациях PRNG, но это ограничивает число начальных состояний.

var seed = 1337 ^ 0xDEADBEEF; // 32-bit seed with optional XOR value
// Pad seed with Phi, Pi and E.
// https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
var rand = sfc32(0x9E3779B9, 0x243F6A88, 0xB7E15162, seed);
for (var i = 0; i < 15; i++) rand();

Выходные данные этих функций PRNG создают положительное 32-разрядное число (от 0 до 2 ³² -1), которое затем преобразуется в число с плавающей запятой в диапазоне от 0 до 1 (0 включительно, 1 исключительно), эквивалентное Math.random(), если вы хотите случайные числа из определенного диапазона, прочитайте эту статью на MDN . Если вам нужны только необработанные биты, просто удалите последнюю операцию деления.

Еще одна вещь, которую стоит отметить, это ограничения JS. Числа могут представлять только целые числа с разрешением до 53 бит. А при использовании побитовых операций это уменьшается до 32. Это затрудняет реализацию алгоритмов, написанных на C или C ++, которые используют 64-битные числа. Для переноса 64-битного кода требуются прокладки, которые могут существенно снизить производительность. Поэтому для простоты и эффективности я рассмотрел только алгоритмы, в которых используется 32-разрядная математика, поскольку она напрямую совместима с JS.

Теперь вперед к генераторам. (Я поддерживаю полный список со ссылками здесь )

sfc32 (простой быстрый счетчик)

sfc32 является частью набора для тестирования случайных чисел PractRand (который он, конечно, проходит). sfc32 имеет 128-битное состояние и очень быстр в JS.

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 - это простой генератор с 32-битным состоянием, но он очень быстрый и имеет хорошее качество (автор утверждает, что он прошел все тесты gjrand testing и имеет полный период ³² , но я не проверял).

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;
    }
}

Я бы порекомендовал это, если вам просто нужен простой, но приличный PRNG и вам не нужны миллиарды случайных чисел (см. « День рождения» ).

xoshiro128 **

По состоянию на май 2018 года, xoshiro128 ** является новым членом семейства Xorshift , от Vigna / Blackman (который также написал xoroshiro, который используется в Chrome). Это самый быстрый генератор, который предлагает 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;
    }
}

Авторы утверждают, что он хорошо проходит тесты на случайность ( хотя и с оговорками ). Другие исследователи отмечают, что некоторые тесты в TestU01 не проходят (особенно LinearComp и BinaryRank). На практике это не должно вызывать проблем при использовании чисел с плавающей запятой (таких как эти реализации), но может вызывать проблемы, если полагаться на необработанные младшие биты.

JSF (Небольшой пост Дженкинса)

Это JSF или «smallprng» Боба Дженкинса (2007), парня, который создал ISAAC и SpookyHash . Он проходит тесты PractRand и должен быть достаточно быстрым, хотя и не таким быстрым, как SFC.

function jsf32(a, b, c, d) {
    return function() {
        a |= 0; b |= 0; c |= 0; d |= 0;
        var t = a - (b << 27 | b >>> 5) | 0;
        a = b ^ (c << 17 | c >>> 15);
        b = c + d | 0;
        c = d + t | 0;
        d = a + t | 0;
        return (d >>> 0) / 4294967296;
    }
}

LCG (он же Lehmer / Park-Miller RNG или MCG)

LCG чрезвычайно быстрый и простой, но качество его случайности настолько низкое, что неправильное использование может вызвать ошибки в вашей программе! Тем не менее, это значительно лучше, чем некоторые ответы, предлагающие использовать Math.sinили Math.PI! Это однострочник, что приятно :).

var LCG=s=>()=>(2**31-1&(s=Math.imul(48271,s)))/2**31;

Эта реализация называется минимальной стандартной ГСЧ, предложенной Пак-Миллером в 1988 и 1993 годах и реализованной в C ++ 11 as minstd_rand. Имейте в виду, что это 31-битное состояние (31 бит дает 2 миллиарда возможных состояний, 32 бита - вдвое больше). Это тот самый тип PRNG, который другие пытаются заменить!

Это сработает, но я бы не стал использовать его, если вам действительно не нужна скорость и вас не волнует качество случайности (в любом случае, что такое случайность?). Отлично подходит для игрового джема или демо или что-то. LCG страдают от начальных корреляций, поэтому лучше отказаться от первого результата 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;

Эти значения LCG получены от: P. L'Ecuyer: Таблица линейных конгруэнтных генераторов разных размеров и с хорошей структурой решетки, 30 апреля 1997 г.

Нет, но вот простой псевдослучайный генератор, реализация Multiply-with-carry, которую я адаптировал из Википедии (с тех пор удалена):

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
: Серьезные недостатки реализации были исправлены

Алгоритм Антти Сыкэри хорош и короток. Сначала я сделал вариант, который заменил Jathascript 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: несколько независимых генераторов случайных чисел. Это особенно важно, если вы хотите, чтобы одновременно выполнялось несколько повторяющихся симуляций.

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

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

Фил Трой

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

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();

Написать свой псевдослучайный генератор довольно просто.

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

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

Поэтому вместо 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))

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

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

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

ran.core.seed(0)
myDist = new ran.Dist.Uniform(0, 1)
samples = myDist.sample(1000)

Я написал функцию, которая возвращает засеянное случайное число, он использует Math.sin для длинного случайного числа и использует начальное число для выбора чисел из этого.

Используйте:

seedRandom("k9]:2@", 15)

он вернет ваш номер, первый параметр - любое строковое значение; твое семя второй параметр - сколько цифр вернет.

     function seedRandom(inputSeed, lengthOfNumber){

           var output = "";
           var seed = inputSeed.toString();
           var newSeed = 0;
           var characterArray = ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','y','x','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','U','R','S','T','U','V','W','X','Y','Z','!','@','#','$','%','^','&','*','(',')',' ','[','{',']','}','|',';',':',"'",',','<','.','>','/','?','`','~','-','_','=','+'];
           var longNum = "";
           var counter = 0;
           var accumulator = 0;

           for(var i = 0; i < seed.length; i++){
                var a = seed.length - (i+1);
                for(var x = 0; x < characterArray.length; x++){
                     var tempX = x.toString();
                     var lastDigit = tempX.charAt(tempX.length-1);
                     var xOutput = parseInt(lastDigit);
                     addToSeed(characterArray[x], xOutput, a, i); 
                }                  
           }

                function addToSeed(character, value, a, i){
                     if(seed.charAt(i) === character){newSeed = newSeed + value * Math.pow(10, a)}
                }
                newSeed = newSeed.toString();

                var copy = newSeed;
           for(var i=0; i<lengthOfNumber*9; i++){
                newSeed = newSeed + copy;
                var x = Math.sin(20982+(i)) * 10000;
                var y = Math.floor((x - Math.floor(x))*10);
                longNum = longNum + y.toString()
           }

           for(var i=0; i<lengthOfNumber; i++){
                output = output + longNum.charAt(accumulator);
                counter++;
                accumulator = accumulator + parseInt(newSeed.charAt(counter));
           }
           return(output)
      }

Простой подход для фиксированного семени:

function fixedrandom(p){
    const seed = 43758.5453123;
    return (Math.abs(Math.sin(p)) * seed)%1;
}

Для числа от 0 до 100.

Number.parseInt(Math.floor(Math.random() * 100))