175

Dúvidas

  1. Como é feita a randomização pelo computador?
  2. Qual algorítimo ou qual base matemática o computador usa para gerar esses números?

Por exemplo:

No JavaScript utilizo o Math.random() ele me retorna diferentes números todas as vezes como por exemplo: 0.8908976025413722, 0.7090631313621998 e etc.

0

7 Respostas 7

175
+50

A única coisa realmente randômica são efeitos quânticos, como o decaimento radioativo (qual dos núcleos vai se partir agora?). E isso é meio complicado de se obter em computadores domésticos.

Vários desses algoritmos (em particular o rand() do C, que muitas linguagens usam) se baseiam em geradores pseudo-randômicos. Eles geram uma sequencia de números que parece aleatória para uma pessoa, mas que são totalmente previsíveis se partirem de uma seed conhecida. São, portanto, péssimos para segurança ou criptografia. Eles pegam uma seed (valor inicial dado, geralmente partindo de uma fonte externa, como a data/hora de início do processo) e aplicam transformações para gerar o próximo valor. A vantagem é que são rápidas. E o fato de serem previsíveis permite que você guarde a seed de um puzzle gerado como seu id, por exemplo, e não tenha que gastar espaço algum com o puzzle em si, basta gerar novamente pela mesma seed.

Por exemplo: (acabo de inventar esse algoritmo, não é bom)

static double seed; // uma seed entre 0 e 1
double random() {
   seed /= 1125899839733759;  // um número primo
   seed *= 18014398241046527; // outro
   seed -= (int)seed;         // normalizar
   return seed;
}

int main() {
    seed = 0.753;
    printf("%f\n", random()); // 0.048001
    printf("%f\n", random()); // 0.768009
    printf("%f\n", random()); // 0.288139
    printf("%f\n", random()); // 0.610224
    printf("%f\n", random()); // 0.763582
}

(coliru)

Um dos algoritmos mais usados para isso é o Mersenne Twister, que é capaz de gerar 219937-1 números antes de repetir a sequencia.

Para qualquer caso desses, é importante que se tome cuidado na escolha da seed. Se um atacante ganha conhecimento da seed usada por você, ele pode prever todos os movimentos do programa. Um exemplo desse tipo de ataque contra um site de poker online pode ser encontrado nesse artigo: How We Learned to Cheat at Online Poker: A Study in Software Security. O ataque se inicia com o conhecimento de que a função Randomize() do Pascal é utilizada e de que ela usa como seed o número de milissegundos desde a meia noite. O problema é que posso chutar o tempo exato em que aconteceu a randomização no servidor (ou seja, a hora que o poker foi iniciado). Considerando que erre 1 minuto para mais ou para menos, são apenas 180.000 possíveis sequencias. Um número extremamente pequeno para um computador, basta testar todas as sequencias possíveis e comparar qual gera as cartas que tenho em mãos. No momento que descobrir qual é a sequencia, é possível extrapolar e conhecer as cartas na mão de todos os jogadores. Conhecimento aprendido: Usar apenas o relógio como fonte de uma seed que deveria ser aleatória e oculta é uma péssima ideia.

Outros métodos se baseiam em fontes de entropia que possa ser obtida do hardware, como por exemplo análises de uso do teclado, movimentação do mouse, tráfego de pacotes na rede, etc. Tendo dados suficientes isso será tão próximo do aleatório quanto possível. No Linux você pode ler dessa fonte através dos pseudo-arquivos /dev/random ou /dev/urandom. Eles são uma boa fonte se você precisa de número randômicos reais e podem ser utilizados para inicializar a seed de um gerador pseudo-randômicos, se conveniente.

7
  • 11
    Cabe lembrar que muitos dos geradores modernos, mesmo não dispondo de acesso a um "gerador randômico externo" (dispositivo eletrônico de eventos quânticos que citou), dispõe de acesso ao relógio. O relógio ajuda a "semear" a randomização sem repetir, e esta presente até em calculadoras. Consultar a memória de dados aleatoriamente (/devs citados) também ajuda e pode misturar dados do relógio, mas requer interrupções e tratamento mais complexos. Commented 13/03/2014 às 11:59
  • 3
    Movimentos brownianos são verdadeiramente aleatórios. Commented 24/03/2014 às 21:30
  • 6
    Obter entropia dos efeitos físicos/quânticos talvez não seja tão difícil. Parte do ruído numa TV ou rádio fora do ar vêm diretamente do Big Bang. Ou seja, dá pra constituir um gerador randômico de qualidade muito boa simplesmente acoplando um rádio fora da estação na placa de som :)
    – epx
    Commented 1/04/2014 às 14:57
  • 6
    Esse negócio do /dev/urandom ser menos seguro é superstição gist.github.com/tarcieri/6347417
    – epx
    Commented 1/04/2014 às 14:59
  • 2
    Aproveitando a dica da interferência da TV como gerador aleatório através de um circuito de RF acoplado ao computador. Usando um microcontrolador qualquer basta construir um pequeno circuito com um fio ou trilha de certo comprimento acoplado a uma das portas analógicas e fazer a leitura da mesma para gerar o SEED do gerador de números aleatórios, a cada leitura da porta analógica esta irá capitar a interferência elétrica presente no ambiente, e até poderá sofrer efeitos capacitivo com a proximidade de objetos metálicos ou o corpo humano.
    – Delfino
    Commented 9/07/2015 às 1:40
64
+100

Os geradores clássicos de números pseudo aleatórios (PRNG) funcionam da seguinte forma (algoritmo LC):

 x1 = (a . x0 + b) mod n

onde x0 é a "semente", ou número aleatório anterior, a e b são constantes escolhidas, e n é o maior número aleatório desejado. Lembrando que mod é a operação de resto da divisão.

Isto é utilizado com números inteiros, provavelmente o Javascript gera um número inteiro de 64 bits ou maior e divide por uma constante antes de retornar via Math.random(), já que nesta função o número vem entre 0 e 1.

A qualidade deste PRNG depende da boa escolha de a e b. Para ver quais as constantes e/ou a implementação exata o jeito é consultar o fonte da implementação Javascript em que você está interessado, se ela for de código-fonte aberto (V8/Node é, Mozilla é, outras não).

Há PRNGs mais modernos que o LC. Mersenne Twister é muito utilizado e recomendado. Como o Math.random() do Javascript não pode ser "semeado", ele pode fazer uso de qualquer PRNG, então só mesmo consultando o fonte para ver qual é.

50

A aleatoriedade está relacionada ao conceito de imprevisibilidade: dado um número (ou sequência de números) você ser incapaz de prever qual será o próximo número. Além disso, outros requisitos podem estar presentes, como a probabilidade de cada número dentro do domínio ser sorteado (que, em geral, deve ser a mesma).

Os computadores em geral são determinísticos, ou seja: o mesmo programa executado duas vezes com todas as entradas idênticas irão produzir duas saídas idênticas. Por essa razão, uma fonte externa é necessária para se produzir resultados realmente aleatórios. Isso não é algo que o computador consiga produzir por si só.

Como uma fonte dessas raramente está presente, diversos algoritmos foram concebidos para produzir sequências de números que são - até certo grau - indistinguíveis de uma sequência aleatória, a partir de um único valor de partida (semente, ou seed). Esse valor de partida tem de ser diferente a cada invocação do programa, mas não precisa necessariamente ser aleatório, por isso uma fonte muito utilizada é o relógio do sistema. Algoritmos desse tipo são chamados de Geradores de Números Pseudo-Aleatórios (PRNG).

Algumas aplicações, como criptografia, exigem que as sequências geradas sejam realmente imprevisíveis sem o conhecimento da(s) fonte(s) externa(s). Um PRNG comum pode ter sua semente "adivinhada" após a observação de um número finito (e computacionalmente falando, não muito grande) de números gerados anteriormente. Isso não é um problema em domínios como simulações (pois basta que a sequência pareça aleatória), mas quando a segurança de um sistema e/ou a confidencialidade de uma comunicação depende dessa aleatoriedade, um algoritmo mais sofisticado se faz necessário (um CSPRNG - PRNG Criptogtraficamente Seguro).

Uma forma de se fazer isso é gerar uma sequência de números pseudo-aleatórios usando como semente uma chave secreta. Isso é feito através de um simples contador (zero, um, dois...) onde cada elemento é criptografado ou hasheado com o auxílio dessa chave. Essa é, inclusive, a maneira como a maioria das cifras de fluxo (stream cipher) funcionam: gere uma sequência aleatória de bytes, e combine essa sequência com os dados usando XOR.

Quando uma semente secreta não está disponível, então só resta recorrer a outras fontes externas, como mencionado anteriormente. Vários eventos do próprio computador podem ser considerados "imprevisíveis", como: a) as teclas digitadas pelo usuário ou o movimento do mouse; b) a data de criação dos diversos arquivos (ou mesmo seu conteúdo); c) os dados históricos de utilização da CPU; etc. Nem sempre a entropia (desordem, imprevisibilidade) desses eventos é suficiente, mas sua combinação com um PRNG pode aumentar amplamente a qualidade do mesmo. Como mencionado em outra resposta, os números gerador por um PRNG comum começam a repetir após um determinado período. Se o mesmo for combinado com dados de fontes externas (mistura, ou mixing) esse período pode ser bastante alongado - o que é suficiente para muitas aplicações práticas.

Por fim, se nada disso for suficiente, só resta o uso de módulos de hardware (provavelmente envolvendo mecânica quântica) ou dados de sistemas externos. O site random.org, por exemplo, gera uma sequência de números aleatórios baseado em informações atmosféricas (atmospheric noise) - que são tão imprevisíveis com a tecnologia atual que podem ser considerados "realmente aleatórios". Naturalmente, não se deve usá-los para operações confidenciais (como a geração de senhas e chaves) pois eles provém de terceiros, mas para aplicações científicas ou talvez sorteios em jogos de azar, eles podem ser uma boa alternativa.

45

A randomização feita pelo Math.random() retorna um valor positivo (maior ou igual a 0) do tipo Number, porém menor que 1, ele é escolhido randomicamente ou pseudo randomicamente com uma distribuição uniforme aproximadamente sobre este alcance, utilizando uma estratégia ou algoritmo dependente de implementação (implementation-dependent).

Aqui está a implementação dele no Engine V8 utilizado pelo Chrome para rodar Javascript:

uint32_t V8::Random() {

    // Gerador de Número aleatório utilizando o algoritmo MWC de George Marsaglia.
    static uint32_t hi = 0;
    static uint32_t lo = 0;

    // Inicialize a descendência utilizando o  system random(). Se uma das
    // descendências nunca deve tornar-se a zero novamente, ou se random() retorna zero
    // nós evitamos ficar presos com zero bits no hi ou no lo, reinicializando eles na demanda.
    if (hi == 0) hi = random();
    if (lo == 0) lo = random();

    // Misturar os bits.
    hi = 36969 * (hi & 0xFFFF) + (hi >> 16);
    lo = 18273 * (lo & 0xFFFF) + (lo >> 16);
    return (hi << 16) + (lo & 0xFFFF);
}

Referências:

Base(Source):

http://dl.packetstormsecurity.net/papers/general/Google_Chrome_3.0_Beta_Math.random_vulnerability.pdf

Resposta Original no Stack Overflow (EN)

E também, aqui está algumas perguntas relacionadas no Stack Overflow (EN):

1
40

A resposta está baseada nos conceitos de "semente aleatória" (ou "seed"), e "geradores de números pseudoaleatórios".

Por que "pseudo"? Porque os números aleatórios que estão aparecendo na sua chamada a Math.random() são na verdade "quase" aleatórios, já que eles se baseiam em uma "semente". Essa semente é uma "base" para a geração de um grupo de números que parecem aleatórios.

Em geral, ela é baseada na data/hora atual, porque é basicamente um número que nunca se repete, e porque existe um forte elemento de aleatoriedade em intervalos pequenos (como milisegundos).

Existem também outras técnicas de geração, como teclas pressionadas pelo usuário no teclado, etc.

36

Um dos algoritmos mais usados em números pseudo-aleatórios por computadores é o GCL também considerado um dos mais simples é o assim denominado gerador congruente linear (GCL), apresentado por D. H. Lehmer em 1949: considere números inteiros m, a, c e s tais que m > 0, 0 ≤ a < m, 0 ≤ a < m e 0 ≤ s < m. Colocando x0 = s, defina recursivamente para cada inteiro n ≥ 0:


xn + 1 = (a xn + c) mod m

Isto é, xn + 1 é o resto da divisão de a xn + c por m. Por exemplo, se m = 10, a = 11, c = 3 e x0 = s = 3, então a x0 + c = 36. Como o resto da divisão de 36 por 10 é 6, segue-se que x1 = 6. Sendo assim, a x1 + c = 69. Como o resto da divisão de 69 por 10 é 9, segue-se que x2 = 9. Prosseguindo-se com este esquema, a partir do número x0 = 3, geramos os números x1 = 6, x2 = 9, x3 = 2, x4 = 5, x5 = 8, x6 = 1, x7 = 4, x8 = 8, x9 = 0, x10 = 3. Note que depois de x10, a sequência de números gerados se repete (com período 10).


resposta baseada em: http://en.wikipedia.org/wiki/Random_number_generation

-3

const express = require('express');

const app = express();

const fs = require('fs');

app.listen(3333, () => { console.log("Server Rodando") }) app.get('/teste', async (req, res) => {

try{
const response = await fetch('https://pokeapi.co/api/v2/pokemon?limit=10');
const data = await response.json();
const pokemon = await Promise.all(data.results.map(async (pokemon) => {
    const pokemonResponse = await fetch(pokemon.url);
    const pokemonData = await pokemonResponse.json();
    const tipos = pokemonData.types.map((type) => type.type.name);
    const golpes = pokemonData.moves.map((move) => move.move.name);
    return {
        nome: pokemonData.name,
        tipos: tipos,
        golpes: golpes.slice(0, 3)
    }
}));
res.status(200).json(pokemon);

fs.writeFile('dado.json', JSON.stringify(pokemon), 'utf8' , (err) => {
    if (err) {
        console.log('Erro ao salvar os dados em um arquivo JSON', err);
        res.status(500).json({ error: 'Erro ao salvar os dados em um arquivo JSON' });
    } else {
        console.log('Dados salvos com sucesso em dados.json');
        res.status(200).json(pokemon);
    }
})

} catch(error) { console.log('Errro ao carregar Api', error); } }); console.log("teste");

1
  • 2
    Boas-vindas Pedro. Poderia explicar como seu codigo responde a pergunta Como é gerada a randomização pelo computador?? Notamos que e a segunda vez que posta o codigo sem nenhum contexto aparente com a pergunta, se isso for um engano recomendamos que primeiro compreenda como funciona o basico do site fazendo o tour e lendo o central de ajuda.
    – Syzoth
    Commented 10/07/2023 às 18:09

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .