Gerações de números pseudo-aleatórios

Eu usei MT19937em um equipamento de teste para gerar valores [0, - 1] de 32 bits uniformemente (não assinados) , com base na implementação mt19937.c do Authors original , para gerar um suprimento (essencialmente inesgotável) de fluxo estatisticamente aleatório de octetos de bits. Isso substitui um CSPRNG, que não é necessário para esses testes específicos. No entanto, recentemente estive considerando os PRNGs - não por causa das propriedades estatísticas como tais (ambos parecem mais do que adequados para minhas necessidades) - mas eles parecem sugerir uma implementação mais eficiente. $2^{32}$ WELL

Eu não tenho o conhecimento matemático dos trabalhos acadêmicos, embora eu pudesse pelo menos seguir a matriz de 'torção' e a transformação de têmpera para o primeiro. No entanto, grande parte do código fornecido pelos autores das WELL-nfunções parece se concentrar na geração de ponto flutuante, com algumas constantes mágicas de ponto flutuante (por exemplo, 2.32830643653869628906e-10). As etapas podem ser omitidas no WELLcódigo para fornecer uma distribuição uniforme de 32 bits? Ou o algoritmo foi projetado / tendencioso especificamente para distribuições de ponto flutuante?

Ou eu estou errado ao pensar que WELLtrará um ganho de desempenho para a geração vetorial em massa do uint32, satisfazendo meus requisitos?

performance c random-number-generation Brett Hale
fonte

Se isso é apenas curiosidade, tudo bem, mas o desempenho real sempre depende do que mais está acontecendo. Se a geração de números aleatórios está consumindo 10% do tempo total e você pode reduzi-lo pela metade, isso gera uma aceleração de 5%, o que pode não valer a pena.

Mike Dunlavey

Talvez fora de tópico, mas também vale a pena considerar geradores no modo contador, como deshawresearch.com/resources_random123.html , que exigem muito, muito menos memória e paralelizam-se trivialmente.

Geoffrey Irving

Como atualização, agora estou me inclinando para os PCGRNGs. Eles são muito mais rápidos, podem fornecer períodos muito longos (bem como múltiplos fluxos) com propriedades estatisticamente excelentes e parecem se recuperar muito rapidamente de IVs ruins.

Brett Hale

Respostas:

Eu imagino que a maioria dos usuários de geradores de números aleatórios esteja interessada em valores de ponto flutuante. É por isso que o Fast Mersenne Twister orientado a SIMD de dupla precisão (dSFMT) existe. No entanto, há um código C mais recente para o WELL RNG que retorna unsigned longvalores. Observando o código, parece que a versão anterior estava sendo lançada unsigned longpara doubleque você possa descobrir o que eles estavam fazendo comparando as duas.

Se você se preocupa principalmente com a velocidade, não acho que esse seja o PRNG para você. A velocidade / desempenho a que os autores se referem não é a rapidez com que o algoritmo gera variáveis aleatórias, mas a rapidez com que ele se recupera de uma inicialização ruim . Isso melhora as propriedades estatísticas do gerador WELL. Consulte a seção 6 da tese de mestrado de Mutsuo Saito (PDF) para obter detalhes sobre o que isso significa. Esses testes são realizados com estados iniciais artificiais de pior caso, portanto, não está claro para mim qual é o efeito em uso geral.

A geração aleatória de números pode ser bastante cara - geralmente apesar da intuição - e é um excelente candidato para otimização, desde que seu código gaste um tempo razoável produzindo valores aleatórios. Em meus próprios testes de desempenho simples (Retina MacBook Pro, OS X 10.9), descobri que o WELL RNG era cerca de um terço mais rápido que o Fast Mersenne Twister (SFMT) orientado a números inteiros atual ao produzir uint32valores. SFMTtambém tem suporte para uint64. Eu também achei o clássico mt19937ar.ccódigo para ser cerca de metade da velocidade como SFMT.

horchler
fonte