Fundamentos da geração de números aleatórios em JavaScript

Ser capaz de gerar (aparentemente) números aleatórios é um requisito essencial para muitas áreas da matemática, estatística, ciências, tecnologia e jogos.

Por exemplo, eles podem ser usados para designar participantes a um grupo em um estudo controlado randomizado, para determinar a saída de um jogo de computador ou para encontrar soluções aproximadas para problemas intratáveis. Eu freqüentemente uso números aleatórios para verificar minhas soluções para problemas estatísticos perfeitamente tratáveis também. Geradores de números aleatórios criptográficos, que não abordaremos aqui, podem ser usados em segurança.

Types of Random Number Generator

Para o propósito deste artigo, pelo menos, podemos pensar na existência de três categorias de coleta de números aleatórios:

• “True” random numbers;
• Pseudorandom numbers;
• Quasirandom sequences.

Os verdadeiros geradores de números aleatórios (TRNGs) (ou hardware) usam processos físicos do mundo real que se acredita serem de natureza aleatória para criar fluxos de números. Eventos de decaimento de uma fonte radioativa, por exemplo, são aleatórios e não correlacionados entre si, o ruído atmosférico também pode ser usado.

Os TRNGs geralmente não são práticos ou convenientes (ou necessários) para muitos propósitos. Uma alternativa muito mais comum é criar um fluxo de números que parecem ser distribuídos aleatoriamente em algum intervalo usando um algoritmo de computador. Esses algoritmos não são verdadeiramente imprevisíveis e, portanto, são chamados de geradores de números pseudoaleatórios (PRNGs).

Finalmente, sequências quasialeatórias são uma coleção finita de números que devem ser representativos de um espaço amostral de alguma forma. Por exemplo, a média da sequência pode ser a mesma (ou muito semelhante) à média conhecida da população. Embora as sequências quasialeatórias sejam interessantes e possam ser úteis, elas não são o foco deste artigo e não serão discutidas mais adiante.

The Standard Uniform Distribution

Geralmente, a saída de um grande número de valores de um gerador de números pseudoaleatórios destina-se a aproximar a distribuição uniforme padrão (SUD) que cobre o intervalo de 0 a 1. Há, no entanto, alguma variação na inclusão de um ou ambos os pontos finais. No mundo conceitual da matemática das distribuições contínuas, basicamente não há diferença entre a distribuição uniforme entre [0,1] (inclui 0 e 1) e a distribuição uniforme entre (0,1) (exclui 0 e 1). No mundo real dos números de ponto flutuante, com apenas um número finito de valores possíveis entre 0 e 1, a diferença é real e pode ser potencialmente problemática. Pode-se, por exemplo, querer usar o número gerado dentro da função logaritmo natural Math.log.

Gerar um número aleatório para outra distribuição geralmente é "apenas" uma questão de usar um ou mais números de um SUD PRNG para produzir um valor apropriado a partir da distribuição de interesse. Dependendo da distribuição final desejada, isso pode envolver uma linha de código ou algo bastante complexo. Para o restante deste artigo, vou me limitar a discutir a geração de números a partir de um SUD PRNG.

Period

Um PRNG útil deve ter um período grande, o que significa que deve ser capaz de produzir um grande número de números sem se repetir. Por exemplo, o Wichmann Hill PRNG de 1982 (mais sobre isso depois) tem um período de quase 7 trilhões de números, enquanto o extremamente popular Mersenne Twister PRNG tem um período de 2 ¹⁹⁹³⁷ a 1 números. O primeiro é considerado bastante curto para os padrões modernos.

O que há de errado com Math.random?

Você pode usar o Math.random integrado do JavaScript regularmente e não ter problemas com ele. No entanto, tem uma grande limitação: sua saída não é reproduzível. Execute o código que utiliza Math.random repetidamente e você obterá um conjunto diferente de resultados a cada vez. Em muitos casos, isso realmente não é um problema. Na verdade, em muitos (na maioria, provavelmente) casos, será exatamente o que você deseja. A imprevisibilidade (para um humano sentado olhando para a saída, pelo menos) é exatamente o que é necessário. Mas às vezes queremos ver o mesmo conjunto de resultados.

Afastando-se do JavaScript por um momento, considere executar um experimento de simulação para um trabalho que você deseja publicar. Talvez você esteja usando C++ ou Java ou R ou... Você quer que seus resultados sejam reproduzíveis. Essas linguagens (e muitas outras) oferecem uma maneira de "semear" o estado inicial de seus PRNGs. Você define a semente de uma forma ou de outra e obtém a mesma sequência de números "aleatórios". Math.random também requer uma semente, simplesmente não há como configurá-la sozinho. A especificação para Math.random também é bastante aberta, permitindo que os fornecedores de navegadores usem "um algoritmo dependente da implementação", desde que a saída seja aproximadamente uniforme no intervalo [0,1].

Do ponto de vista pessoal, sou um grande fã da visualização interativa de dados baseada em navegador para comunicar dados e conceitos. Isso pode incluir simulação; Há limites para o que é prático em um navegador, mas os web workers podem ajudar. A simulação freqüentemente requer números aleatórios. Se os números aleatórios não forem reproduzíveis, as condições para uma simulação não poderão ser executadas novamente. Existem muitos outros casos de uso também, como uma animação repetível, e o JavaScript não é mais apenas a linguagem de programação do navegador.

PRNGs problemáticos

Até agora, pulei como funcionam os PRNGs de distribuição uniforme. Tudo tem sido uma espécie de caixa preta: você chama uma função uma ou mais vezes, possivelmente definindo uma semente, e então alguns números pseudoaleatórios aparecem. O problema é que criar um bom PRNG é difícil. Existem milhares de artigos sobre o tema e vários métodos. E vários casos em que pessoas que sabem muito mais sobre esse tópico do que eu parecem ter entendido as coisas erradas. Por exemplo...

RANDU

RANDU é um "gerador congruencial linear" (LCG) desenvolvido pela IBM na década de 1950. Os LCGs usam uma relação de recorrência da seguinte forma para gerar novos números pseudoaleatórios:

No caso de RANDU, c é 0, a é 65.539 e m é 2 ³¹. Como c é 0, RANDU é membro de um subconjunto de LCGs chamados "geradores congruenciais multiplicativos" (MCG). Para obter um número no intervalo de 0 a 1 (como é desejado para uma substituição de Math.random), basta dividir o resultado da relação de recorrência RANDU por m. Uma implementação JavaScript (que você definitivamente não deve usar!) pode ser algo assim:

var randu = function(seed){

   "use strict";
   
   if(!isFinite(seed)){
      throw new Error("Seed not a finite number");
   }
		   
   var x = Math.round(seed);
   var a = 65539;
   var m = Math.pow(2, 31);

   if(x<1 || x≥m){
      throw new Error("Seed out of bounds");
   }

   return function(){
      x = (a*x)%m;
      return x/m;
   };
    
};

A paridade do valor gerado pela relação de recorrência em RANDU nunca muda. Ou seja, uma semente ímpar dá origem apenas a valores ímpares de x, enquanto uma semente par dá origem apenas a valores pares de x. Esta não é exatamente uma propriedade desejável, mas há problemas maiores.

O período de um LCG é no máximo m, mas para RANDU é muito menor do que isso e depende da paridade da semente. Para sementes ímpares, são mais de 536 milhões, mas para sementes pares podem ser apenas 16.384.

Há outra razão para não se preocupar com uma semente uniforme: um método comum e simples para avaliar a aleatoriedade de um gerador é plotar pares de valores sucessivos como um gráfico de dispersão. Um bom PRNG deve preencher um quadrado de 1 por 1 de maneira bastante uniforme. Com 10.000 números aleatórios, 5.000 pontos e uma semente de 1, tudo parece razoável. (Você pode pensar em "x" como se referindo aos valores em posições de índice par em uma matriz (indexada com 0) de 10.000 números aleatórios. Ou seja, os índices 0, 2, 4, 6 ... 9,996, 9,998. Os pontos no gráfico de dispersão são feitos combinando com o próximo índice ímpar (1, 3, 5, 7 ... 9.997, 9999) valor "y".)

Com algumas sementes uniformes, algo bem diferente. Abaixo está um gráfico de dispersão para a semente 32.768.

Claramente, não temos apenas um déficit de pontos no caso de sementes pares. Em alguns casos, temos relações inequívocas entre valores vizinhos.

Seria simples o suficiente adaptar a função randu acima para rejeitar até mesmo sementes, dando uma mensagem de erro apropriada. Infelizmente, as sementes de probabilidades também mostram estrutura. Para ver isso, precisamos apenas estender a ideia do gráfico de dispersão para três dimensões, observando trigêmeos de números aleatórios sucessivos. Os gráficos de dispersão 3D são frequentemente bastante inúteis. Os dados RANDU fornecem uma espécie de exceção a essa regra. (Aqui os índices para valores "x" são 0, 3, 6, 9... 9.993, 9.996, os índices para valores "y" são 1, 4, 7, 10... 9.994, 9997 e os índices para valores "z" são 2, 5, 8, 11 ... 9,995, 9,998.)

Em vez de preencher a caixa aproximadamente uniformemente, trigêmeos de números estão todos em um dos 15 planos, independentemente da semente! (Na verdade, para a semente par 32.768 é pior do que isso.) Podemos comparar isso com os resultados de Math.random (usei o Chrome para isso); A diferença é gritante.

Um problema geral com gráficos de dispersão 3D é que a visibilidade da estrutura no gráfico pode depender do ângulo de visão. De certos ângulos, a estrutura no enredo RANDU está oculta. Este pode ser o caso de Math.random. Para ajudar com esse problema, criei uma versão interativa que permite escolher um PRNG (e, quando apropriado, uma ou mais sementes) e visualizar os resultados usando WebGL Esta demonstração pode ser encontrada aqui e a caixa de números aleatórios pode ser girada (usando o mouse) e vista de diferentes ângulos. Ainda não encontrei nenhum sinal óbvio de estrutura ao usar o Math.random em vários navegadores (Chrome, Firefox, Maxthon, IE, Edge e Opera na área de trabalho e Safari no iOS).

O aparecimento de estruturas de treliça em 3 ou mais dimensões existe para todos os MCGs, mas é particularmente ruim para RANDU. É conhecido desde a década de 1960. Apesar disso, o RANDU ainda era usado na década de 1970 e alguns resultados de simulação daquela época deveriam, talvez, ser vistos com ceticismo.

Distinguir-se

Você pode estar se perguntando se os problemas com PRNGs foram confinados aos anos 1960 e 70? A resposta curta a esta pergunta é "não". Após críticas ao seu antigo gerador de números aleatórios, a Microsoft mudou para o PRNG de Wichmann-Hill para Excel 2003. O gerador WH (publicado pela primeira vez em 1982) combina três MCGs para superar algumas das deficiências de MCGs únicos (como um período relativamente curto e os planos de rede e hiperplanos vistos quando se olha para grupos de valores vizinhos). Uma implementação rápida de JavaScript do WH pode ser semelhante à seguinte:

var wh = function(seeds){
  
   "use strict";

   if(seeds.length<3){
      throw new Error("Not enough seeds");
   }

   var xA = Math.round(seeds[0]);
   var aA = 171;
   var mA = 30269;

   var xB = Math.round(seeds[1]);
   var aB = 172;
   var mB = 30307;

   var xC = Math.round(seeds[2]);
   var aC = 170;
   var mC = 30323;
   
   if(!isFinite(xA) || !isFinite(xB) || !isFinite(xC)){
      throw new Error("Seed not a finite number");
   }

   if(Math.min(xA,xB,xC)<1 || xA≥mA || xB≥mB || xC≥mC){
      throw new Error("Seed out of bounds");
   }  

   return function(){
      xA = (aA*xA)%mA;
      xB = (aB*xB)%mB;
      xC = (aC*xC)%mC;
      return (xA/mA + xB/mB + xC/mC) % 1;
   };
	  
};

Novamente, podemos procurar estrutura ao plotar conjuntos de valores vizinhos em duas ou três dimensões:

Embora isso claramente não seja suficiente para dizer se temos ou não um bom gerador de números aleatórios, os gráficos acima pelo menos parecem razoáveis. (Você também pode marcar a caixa tridimensional na demonstração do WebGL mencionada acima.) No entanto, a implementação original do algoritmo WH para a função RAND no Excel ocasionalmente cuspia números negativos!

O algoritmo WH falha em vários testes mais modernos e rigorosos de PRNGs e parece que a Microsoft passou a usar o popular (mas mais complexo) algoritmo Mersenne Twister.

V8

Anteriormente, usei a saída da implementação do Math.random do Chrome para ilustrar como deve ser a distribuição de trigêmeos de números aleatórios quando plotada como um gráfico de dispersão tridimensional. No entanto, o algoritmo usado pelo V8, o mecanismo JavaScript do Chrome, mostrou recentemente ser falho. Especificamente, ele reproduziu as mesmas sequências de caracteres "aleatórias" com frequência muito maior do que deveria, como este artigo longo, mas informativo, descreve. Os desenvolvedores do V8 mudaram prontamente o algoritmo usado e o problema parece ter sido corrigido no Chrome desde a versão 49.

Speed

Outra consideração antes de tentar "desenvolver seu próprio" JavaScript PRNG é a velocidade. Deve-se esperar que o Math.random seja altamente otimizado. Por exemplo, alguns testes muito aproximados usando vários navegadores mostraram que Math.random é ~ 3 vezes mais rápido na produção de 100.000 números aleatórios do que a implementação simples do WH acima. Dito isso, ainda estamos falando da ordem de apenas dezenas de milissegundos (pelo menos no Chrome e no Firefox no meu laptop), então isso pode não ser um gargalo, mesmo que você precise de um grande número de números aleatórios. Obviamente, PRNGs mais complexos com melhores propriedades estatísticas podem ser mais lentos.

Conclusões

Eu mal toquei a superfície aqui. Eu só olhei para alguns PRNGs simples e mostrei que eles ainda podem ser problemáticos. Existem algoritmos muito mais complicados para PRNGs por aí, alguns que passaram por um grande número de testes estatísticos bastante rigorosos. E alguns deles já têm implementações JavaScript de código aberto.

Se você não precisa de reprodutibilidade, Math.random pode ser bom para todas as suas necessidades de números aleatórios. De qualquer forma, se a confiabilidade do seu gerador de números aleatórios for fundamental para o funcionamento do seu site, você deverá realizar as verificações relevantes. No caso do Math.random, isso significa fazer check-in de todos os navegadores de destino, pois a especificação JavaScript não especifica um algoritmo específico que os fornecedores devem usar.

Experimente nossos controles JavaScript HTML5 para seus aplicativos da web e aproveite imediatamente seus impressionantes recursos de visualização de dados. Baixe a avaliação gratuita hoje.