Algoritmos de geração de números pseudoaleatórios

12

Quais algoritmos são usados ​​em geradores de números aleatórios modernos e de boa qualidade?

algorithms random-variable random-generation Mehper C. Palavuzlar
fonte
11
Alterado como "variável aleatória" para "variável aleatória" para consistência com perguntas semelhantes.
whuber

Respostas:

10

Em R, a configuração padrão para geração de número aleatório é:

  1. Para U (0,1), use o algoritmo de Mersenne-Twister
  2. Para números guassianos, use a inversão numérica da função de distribuição normal padrão.

Você pode facilmente verificar isso, viz.

> RNGkind()
[1] "Mersenne-Twister" "Inversion"

É possível alterar o gerador padrão para outros PRNGs, como Super-Duper, Wichmann-Hill, Marsaglia-Multicarry ou mesmo um PRNG fornecido pelo usuário. Veja o? RNGkind para mais detalhes. Eu nunca precisei alterar o PRNG padrão.

A biblioteca C GSL também usa o Mersenne-Twister por padrão.

csgillespie
fonte
Você tem certeza do seu segundo ponto, gerando variáveis ​​aleatórias normais ao inverter o CDF? O inverso do CDF normal é uma função bastante cara de avaliar. Imagino que o método de Box-Muller seria mais rápido. Mais rápido ainda seria o método de zigurate de Marsaglia para gerar normais.
John D. Cook
Eu também acho isso suspeito. O Zigurate de Marsaglia é o padrão no Matlab, e não consigo imaginar o Matlab sendo melhor que R no campo da geração de números aleatórios.
precisa saber é o seguinte
@ John De fato, o método polar está disponível em R, veja o pacote setRNG.
chl
3

O PNG Xorshift criado por George Marsaglia. Seu período (2 ^ 128-1) é muito mais curto que o Mersenne-Twister, mas o algoritmo é muito simples de implementar e se presta à paralelização. Apresenta bom desempenho em arquiteturas de muitos núcleos, como chips DSP e Tesla da Nvidia.

brotchie
fonte
Isso seria bom para implementar em GPUs? Link para detalhes, referências?
DarenW
2
Thomas, Howes, Luk - 2009 - Uma comparação de CPUs, GPUs, FPGAs e matrizes de processadores massivamente paralelos para geração aleatória de números. doi.acm.org/10.1145/1508128.1508139 . Discussão + benchmarks de um conjunto de PNGs em execução em CPU, GPU, FPGA e matrizes de processador massivamente paralelo.
Brotchie 9/08/10
Talvez também o RNG da L'Ecuyer com múltiplos fluxos ( j.mp/bzJSlm )?
chl
3

Em http://prng.di.unimi.it/, você pode encontrar vários geradores de números aleatórios testados usando o TestU01, o moderno conjunto de testes para geradores de números pseudo-aleatórios que substituíram o obstáculo e o dieharder. Você pode escolher e escolher.

seba
fonte