Semeando o gerador de números aleatórios em Javascript

É possível propagar o gerador de números aleatórios (Math.random) em Javascript?

Não, não é, mas é bastante fácil escrever seu próprio gerador ou, melhor ainda, usar um já existente. Confira: esta questão relacionada .

Além disso, consulte o blog de David Bau para obter mais informações sobre propagação .

OBSERVAÇÃO: Apesar (ou melhor, por causa da) sucessão e elegância aparente, esse algoritmo não é de forma alguma de alta qualidade em termos de aleatoriedade. Procure, por exemplo, os listados nesta resposta para obter melhores resultados.

(Originalmente adaptado de uma ideia inteligente apresentada em um comentário para outra resposta.)

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

Você pode definir seedqualquer número, evite zero (ou qualquer múltiplo de Math.PI).

A elegância dessa solução, na minha opinião, vem da falta de números "mágicos" (além de 10000, que representa a quantidade mínima de dígitos que você deve jogar fora para evitar padrões estranhos - veja resultados com os valores 10 , 100 , 1000 ) Brevidade também é legal.

É um pouco mais lento que Math.random () (por um fator de 2 ou 3), mas acredito que seja tão rápido quanto qualquer outra solução escrita em JavaScript.

Eu implementei uma série de boas, curtas e rápidas funções gerador de números Pseudoaleatórios (PRNG) em JavaScript simples. Todos eles podem ser semeados e fornecer números de boa qualidade.

Antes de tudo, tome cuidado para inicializar seus PRNGs corretamente.A maioria dos geradores abaixo não possui procedimento de geração de sementes embutido (por uma questão de simplicidade), mas aceita um ou mais valores de 32 bits como estado inicial do PRNG. Sementes similares (por exemplo, uma semente simples de 1 e 2) podem causar correlações em PRNGs mais fracos, resultando em resultados com propriedades semelhantes (como níveis gerados aleatoriamente sendo semelhantes). Para evitar isso, é uma boa prática inicializar PRNGs com uma semente bem distribuída.

Felizmente, as funções de hash são muito boas para gerar sementes para PRNGs a partir de strings curtas. Uma boa função de hash gera resultados muito diferentes, mesmo quando duas seqüências são semelhantes. Aqui está um exemplo baseado na função de mixagem do 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;
    }
}

Cada chamada subseqüente à função de retornoxmur3 produz um novo valor de hash "aleatório" de 32 bits para ser usado como uma semente em um PRNG. Veja como você pode usá-lo:

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

Como alternativa, basta escolher alguns dados fictícios para preencher a semente e avançar o gerador algumas vezes (12 a 20 iterações) para misturar completamente o estado inicial. Isso geralmente é visto em implementações de referência de PRNGs, mas limita o número de estados iniciais.

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

A saída dessas funções PRNG produz um número positivo de 32 bits (0 a 2 ³² -1), que é convertido em um número de ponto flutuante entre 0-1 (0 inclusivo, 1 exclusivo) equivalente a Math.random(), se você quiser números aleatórios de um intervalo específico, leia este artigo no MDN . Se você deseja apenas os bits brutos, basta remover a operação de divisão final.

Outra coisa a se notar são as limitações do JS. Os números podem representar apenas números inteiros até a resolução de 53 bits. E ao usar operações bit a bit, isso é reduzido para 32. Isso dificulta a implementação de algoritmos escritos em C ou C ++, que usam números de 64 bits. Portar código de 64 bits requer calços que podem reduzir drasticamente o desempenho. Portanto, por uma questão de simplicidade e eficiência, considerei apenas algoritmos que usam matemática de 32 bits, pois é diretamente compatível com JS.

Agora, em diante para os geradores. (Eu mantenho a lista completa com referências aqui )

sfc32 (contador rápido simples)

O sfc32 faz parte do conjunto de testes de números aleatórios PractRand (que é aprovado, é claro). O sfc32 possui um estado de 128 bits e é muito rápido em 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

O Mulberry32 é um gerador simples com um estado de 32 bits, mas é extremamente rápido e tem boa qualidade (o autor declara que passa em todos os testes do conjunto de testes gjrand e possui um período completo de ^{32 32} , mas não verifiquei).

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

Eu recomendaria isso se você só precisa de um PRNG simples, mas decente, e não precisa de bilhões de números aleatórios (consulte Problema no aniversário ).

xoshiro128 **

A partir de maio de 2018, xoshiro128 ** é o novo membro da família Xorshift , de Vigna / Blackman (que também escreveu xoroshiro, usado no Chrome). É o gerador mais rápido que oferece um estado de 128 bits.

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

Os autores afirmam que passam bem nos testes de aleatoriedade ( embora com ressalvas ). Outros pesquisadores apontaram que falha em alguns testes no TestU01 (particularmente LinearComp e BinaryRank). Na prática, não deve causar problemas quando são utilizados carros alegóricos (como essas implementações), mas pode causar problemas se depender dos bits baixos brutos.

JSF (jejum pequeno de Jenkins)

Esse é o JSF ou 'smallprng' de Bob Jenkins (2007), o cara que criou o ISAAC e o SpookyHash . Ele passa nos testes do PractRand e deve ser bastante rápido, embora não tão rápido quanto o 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 (também conhecido como Lehmer / Park-Miller RNG ou MCG)

O LCG é extremamente rápido e simples, mas a qualidade de sua aleatoriedade é tão baixa que o uso inadequado pode realmente causar bugs no seu programa! No entanto, é significativamente melhor do que algumas respostas sugerindo o uso Math.sinou Math.PI! É uma frase única, o que é legal :).

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

Essa implementação é chamada de RNG padrão mínimo, conforme proposto por Park-Miller em 1988 e 1993 e implementado no C ++ 11 como minstd_rand. Lembre-se de que o estado é de 31 bits (31 bits fornecem 2 bilhões de estados possíveis, 32 bits fornecem o dobro disso). Este é o tipo de PRNG que outros estão tentando substituir!

Funcionará, mas eu não o usaria a menos que você realmente precise de velocidade e não se importe com a qualidade da aleatoriedade (o que é aleatório, afinal?). Ótimo para um game jam ou uma demo ou algo assim. Os LCGs sofrem correlações de sementes, portanto, é melhor descartar o primeiro resultado de um LCG. E se você insistir em usar um LCG, adicionar um valor de incremento pode melhorar os resultados, mas provavelmente é um exercício de futilidade quando existem opções muito melhores.

Parece haver outros multiplicadores que oferecem um estado de 32 bits (maior espaço de estado):

var LCG=s=>()=>(s=Math.imul(741103597,s)>>>0)/2**32;
var LCG=s=>()=>(s=Math.imul(1597334677,s)>>>0)/2**32;

Esses valores de LCG são de: P. L'Ecuyer: Uma tabela de Geradores Lineares Congruenciais de diferentes tamanhos e boa estrutura de treliça, 30 de abril de 1997.

Não, mas aqui está um simples gerador de pseudo-aleatório, uma implementação do Multiply-with-carry I adaptada da Wikipedia (foi removida desde):

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

EDIT: função de semente corrigida, redefinindo m_z
EDIT2: falhas graves de implementação foram corrigidas

O algoritmo de Antti Sykäri é bom e curto. Inicialmente, fiz uma variação que substituiu Math.random do Javascript quando você chama Math.seed (s), mas Jason comentou que retornar a função seria melhor:

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

Isso fornece outra funcionalidade que o Javascript não possui: vários geradores aleatórios independentes. Isso é especialmente importante se você quiser ter várias simulações repetíveis em execução ao mesmo tempo.

Por favor, veja o trabalho de Pierre L'Ecuyer desde o final dos anos 80 e início dos anos 90. Há outros também. Criar um gerador de números aleatórios (pseudo) por conta própria, se você não for um especialista, é muito perigoso, porque há uma alta probabilidade de os resultados não serem estatisticamente aleatórios ou terem um período pequeno. Pierre (e outros) reuniram alguns bons (pseudo) geradores de números aleatórios que são fáceis de implementar. Eu uso um de seus geradores LFSR.

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

Phil Troy

Combinando algumas das respostas anteriores, esta é a função aleatória inicial que você está procurando:

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

Escrever seu próprio gerador pseudo-aleatório é bastante simples.

A sugestão de Dave Scotese é útil, mas, como apontado por outros, não é distribuída de maneira uniforme.

No entanto, não é por causa dos argumentos inteiros do pecado. É simplesmente por causa do alcance do pecado, que passa a ser uma projeção unidimensional de um círculo. Se você escolher o ângulo do círculo, ele será uniforme.

Portanto, em vez de sin (x), use arg (exp (i * x)) / (2 * PI).

Se você não gosta da ordem linear, misture um pouco com xor. O fator real também não importa tanto.

Para gerar n números pseudo-aleatórios, pode-se usar o código:

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

Observe também que você não pode usar sequências pseudo-aleatórias quando a entropia real for necessária.

Atualmente, muitas pessoas que precisam de um gerador de números aleatórios sem fio em Javascript estão usando o módulo aleatório de sementes de David Bau .

Math.randomnão, mas a biblioteca executada resolve isso. Ele tem quase todas as distribuições que você pode imaginar e suporta a geração de números aleatórios semeados. Exemplo:

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

Eu escrevi uma função que retorna um número aleatório semeado, ele usa Math.sin para ter um número aleatório longo e usa a semente para escolher números disso.

Usar :

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

retornará seu número inicial, o primeiro parâmetro é qualquer valor de string; sua semente. o segundo parâmetro é quantos dígitos retornarão.

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

Uma abordagem simples para uma semente fixa:

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

Para um número entre 0 e 100.

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