Embora existam muitas perguntas sobre código de golfe envolvendo aleatoriedade, ainda não vi uma que realmente solicite a construção de um gerador de números pseudoaleatórios algorítmicos. Existe um que pede para você gerar um fluxo de bits, mas os testes de aleatoriedade fornecidos nesse não foram muito rigorosos e não são códigos de golfe.

O programa que você escreve terá uma única função que pode ser chamada que retornará um número inteiro aleatório de 0 a 4294967295. Essa função não deve chamar bibliotecas ou outras funções que também não foram gravadas como parte do programa, especialmente chamadas para / dev / random ou a biblioteca rand () interna de um idioma. Mais especificamente, você está limitado aos operadores básicos do idioma em que está trabalhando, como aritmética, acesso à matriz e instruções de controle de fluxo condicional.

A pontuação do seu programa é calculada da seguinte forma:

Score = C / R

Onde C é o comprimento do código em caracteres e R é o número de testes de Diehard que o seu gerador passa (se o gerador de números aleatórios não passar em pelo menos um teste de Diehard, sua pontuação é infinita e é desqualificada). Seu gerador passa no teste Diehard se o arquivo gerado fornecer uma faixa de valores P que parecem distribuídos uniformemente ao longo do intervalo [0, 1).

Para calcular R, use seu gerador de números aleatórios com sua semente padrão para gerar um arquivo de dados binários de 16 MB. Cada chamada da função retorna quatro bytes; se sua função for muito lenta para retornar bytes, isso fará com que uma troca atinja uma pontuação baixa pela dificuldade em testar. Em seguida, execute-o através dos testes Diehard e verifique os valores-P fornecidos. (Não tente implementá-las você mesmo; use as fornecidas aqui )

Menor pontuação ganha, é claro.

Mathematica, 32/15 = 2,133

x=3;Mod[x=Mod[x^2,28!-67],2^32]&

Uma implementação direta do BBS .

Arquivo binário gerado com:

f = %; (* assigns anonymous function declared in the previous expression to f *)
Export["random.bin", Array[f, 2^22], "UnsignedInteger32"];

Resumo dos Resultados:

 1. BIRTHDAY SPACINGS TEST           .684805
 2. OVERLAPPING 5-PERMUTATION TEST   .757608/.455899
 3. BINARY RANK TEST                 .369264/.634256
 4. BINARY RANK TEST                 .838396
 5. THE BITSTREAM TEST                (no summary p-value)    
 6. OPSO, OQSO and DNA                (no summary p-value)
 7. COUNT-THE-1's TEST               .649382/.831761
 8. COUNT-THE-1's TEST                (no summary p-value)
 9. PARKING LOT TEST                 .266079
10. MINIMUM DISTANCE TEST            .493300
11. 3DSPHERES TEST                   .492809
12. SQEEZE                           .701241
13. OVERLAPPING SUMS test            .274531
14. RUNS test                        .074944/.396186/.825835/.742302
15. CRAPS TEST                       .403090/.403088/.277389

Cheio random.binaqui.

Arquivo de log completo aqui.

Perl 28/13 ~ 2,15

sub r{$s^=~($s^=$s/7215)<<8}

arquivo de log aqui

Perl 29/13 ~ 2.23

sub r{$s^=~($s^=$s<<8)/60757}

arquivo de log aqui

Isso é uma variação de um Xorshift , usando a divisão de ponto flutuante em vez de um deslocamento à direita. Ambos foram aprovados em 13 de 15 testes, sendo reprovados apenas nos testes 6 e 7.

Não sei exatamente quanto tempo dura o ciclo, mas como o código a seguir não termina em um curto período de tempo, é provável que o 2 ³² esteja completo :

$start = r();
$i++ while $start != r();
print $i;

Perl 39/10 = 3,9

$s=$^T;sub r{~($s=$s*$s%4294969373)||r}

Nota: se você estiver procurando por um PRNG de estilo Blum-Blum-Shub, a solução de Keith Randall é muito melhor do que qualquer um deles.

Como na minha solução original abaixo, esta também é uma implementação do Blum Blum Shub, com uma grande diferença. Eu uso um módulo um pouco maior que 2 ³² ( M = 50971 • 84263 ) e, sempre que um valor é encontrado, ele não é um número inteiro válido de 32 bits (ou seja, maior que 2 ³² ), ele retorna o próximo valor no rotação em vez disso. Em essência, esses valores são eliminados, deixando o restante da rotação imperturbável, resultando em uma distribuição quase uniforme.

Parece ter ajudado. Além de passar nos mesmos 9 testes de antes, agora também passa no teste de Distância Mínima de forma convincente. Um arquivo de log de amostra pode ser encontrado aqui .

Perl 33/9 ~ 3,67 (Inválido?)

 $s=$^T;sub r{$s=$s*$s%4294951589}

Nota: esta solução pode ser considerada inválida, pois os 0,00037% mais altos do intervalo nunca serão observados.

Uma implementação rápida e suja do Blum Blum Shub . Eu reivindico os seguintes resultados:

 1. passed - Birthday Spacings
 2. FAILED - Overlapping Permutations
 3. passed - Ranks of 31x31 and 32x32 Matrices
 4. passed - Ranks of 6x8 Matrices
 5. FAILED - Monkey Tests on 20-bit Words
 6. FAILED - Monkey Tests OPSO, OQSO, DNA
 7. FAILED - Count the 1s in a Stream of Bytes
 8. passed - Count the 1s for Specific Bytes
 9. passed - Parking Lot Test
10. FAILED - Minimum Distance Test
11. passed - Random Spheres Test
12. FAILED - The Squeeze Test
13. passed - Overlapping Sums Test
14. passed - Runs Test
15. passed - The Craps Test

Um arquivo de log de amostra pode ser encontrado aqui , fique à vontade para contestar qualquer um dos resultados. O arquivo para diehard pode ser gerado da seguinte maneira:

print pack('N', r()) for 1..4194304

e, em seguida, canalize a saída em um arquivo. Parece que a Distância mínima pode ter passado, mas se você executá-la várias vezes, é sempre muito próxima de 1,0 , o que indica falha.

Detalhes

Em geral, o Blum Blum Shub é um péssimo PRNG, mas seu desempenho pode ser melhorado com a escolha de um bom módulo. O M que escolhi é 7027 • 611207 . Ambos os fatores primos, p e q , têm resíduo modular 3 (mod 4) e gcd (φ (p-1), φ (q-1)) = 2 , que é o mais baixo possível.

Embora esses sejam os únicos critérios listados na página da wiki, isso não parece suficiente. Quase todo o módulo que tentei falhou em todos os testes. Mas há alguns que passarão em alguns dos testes, e o que eu escolhi parece ser excepcionalmente bom, por qualquer motivo.

Como observação final, o Teste 5, por si só, parece ser um bom indicador de quão bom é o PRNG. Se ele quase não passar no Teste 5, falhará espetacularmente com o restante.

BÔNUS: Perl 62/14 ≈ 4.43

$t=$^T;sub r{$t|=(($s=$s/2|$t%2<<31)^($t/=2))<<31for 1..37;$t}

Apenas para geeks, esta é uma versão de 32 bits do PRNG usada no Tetris for NES original. Surpreendentemente, ele passa em 14 dos 15 testes!

 1. passed - Birthday Spacings
 2. passed - Overlapping Permutations
 3. passed - Ranks of 31x31 and 32x32 Matrices
 4. passed - Ranks for 6x8 Matrices
 5. passed - Monkey Tests on 20-bit Words
 6. passed - Monkey Tests OPSO, OQSO, DNA
 7. FAILED - Count the 1s in a Stream of Bytes
 8. passed - Count the 1s for Specific Bytes
 9. passed - Parking Lot Test
10. passed - Minimum Distance Test
11. passed - Random Spheres Test
12. passed - The Squeeze Test
13. passed - Overlapping Sums Test
14. passed - Runs Test
15. passed - The Craps Test

Arquivo de log de amostra pode antes aqui .

É certo que o 1..37bit não é uma transcrição exata. Na versão original, a rotina de entropia é atualizada 60 vezes por segundo e depois consultada em intervalos aleatórios, em grande parte dependente da entrada do usuário. Para quem quer desmontar a ROM, a rotina de entropia começa em 0xAB47.

Pseudo-código no estilo Python:

carry = entropy_1 & 1
entropy_1 >>= 1
entropy_2 = (entropy_2 >> 1) | (carry << 31)
carry = (entropy_1 & 1) ^ (entropy_2 & 1)
entropy_1 |= carry << 31

Python, 46/15 = 3.0666

v=3
def R():global v;v=v**3%(2**32-5);return v

Usa exponenciação modular para gerar aleatoriedade. 2 ** 32-5 é o maior primo menor que 2 ^ 32. (O mesmo acordo com a impossibilidade de executar o teste nº 2).

Ruby, 32/15 = 2,1333

Esta é a solução de Keith Randall, implementada em Ruby.

$v=3;def R;$v=$v**3%(2**32-5)end

C # 144/15 = 9,6

uint a=15,b=26,y;uint q(int n){y=(a*1414549U+876619U)^(b*889453U+344753U);b=a;a=y>>12;return(a%256)<<n;}uint r(){return q(24)|q(16)|q(8)|q(0);}

Isso passou em todos os testes.

Com menos caracteres, ele passa no TestU01.

Resultado: http://codepad.org/iny6usjV

    uint a = 15;
    uint b = 26;

    byte prng8()
    {
        uint y = ((a * 1414549U + 876619U) ^ (b * 889453U + 344753U)) >> 12;
        b = a;
        a = y;
        return (byte)y;
    }

    uint prng32()
    {
        return ((uint)prng8() << 24) | ((uint)prng8() << 16) | ((uint)prng8() << 8) | (uint)prng8();
    }

C # - 103/14 = 7,36

double j=999;uint N(){uint i=0,n=0;for(;i++<4;n=n*256+(uint)j%256)for(j/=277;j<100000;j*=j);return n;}

Resultados

Passa em todos, exceto no teste nº 6
Veja os resultados em http://codepad.org/k1NSoyQW

Explicação

O C # simplesmente não pode competir com Ruby e Python pela concisão, como sempre, mas eu gostei de tentar. Certamente existem outros valores que também funcionarão (ou seja, o valor inicial para j = 999 e o divisor = 277). Eu os escolhi após uma breve experimentação.

Com wrapper de criação de arquivo

class R
{
    public static void Main(string[] args)
    {
        var r = new R();
        using (var f = new System.IO.FileStream(".\\out.bin", System.IO.FileMode.Create, System.IO.FileAccess.Write, System.IO.FileShare.Read))
        using (var b = new System.IO.BinaryWriter(f))
        {
            for (long i = 0; i < 12 * 1024 * 1024; i += 4)
            {

                b.Write(r.N());
            }
        }
    }

    double j = 999;

    uint N()
    {
        uint i = 0, n = 0;
        for (; i++ < 4; n = n * 256 + (uint)j % 256)
            for (j /= 277; j < 100000; j *= j) ;
        return n;
    }

}

Python, 41/15 = 2.73333

v=0
def R():global v;v=hash(`v`);return v

É meio trapacear usando a função de hash embutida, mas é embutida, então não há mais trapaça do que usar outras embutidas, como len. Por outro lado, me dói ter que pagar pela global v;declaração ...

Passa em todos os testes da Diehard (tive um problema com o teste nº 2, SEGVs na minha máquina OSX. Para minha pontuação, suponho que ele passará).

Aqui está um driver para gerar o arquivo de 16 MB:

import sys
for i in xrange(1<<22):
  r=R()
  sys.stdout.write('%c%c%c%c'%(r&255, r>>8&255, r>>16&255, r>>24&255))

C, 38/15 = 2,533

long long x;f(){return(x+=x*x+9)>>32;}

Não consegui que os testes Diehard funcionassem na minha máquina, mas ele passou no pacote PractRand com até 8 GB de saída, portanto presumo que passaria em todos eles.

Brain-Flak , 344 / (pendente)

<>((()()){})<> push the amount of iterations to do for the PRNG
(((((((((((((((((((((((((((((((((((()()()){}()){})){}{}){()()()()({}[()])}{})){}{})){}{})()){}{})()){}{})){}{})){}{}){}())){}{})){}{})()){}{})()){}{})){}{})){}{})()){}{})()){}{}) push M (one of the values for the Blum Blum Shub PRNG
((((((((((((()()()){}){}){})){}{}){()({}[()])}{}){}())){}{})()){}{}) push s see above
<>{({}[()])<>starts the loop
(({({})({}[()])}{}) squares the current number
(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]({}))mods by M
<>}{}<>loop ends

Experimente online!

Isso funciona bem, mas os links de testes obstinados estão todos quebrados :( então, até obtermos novos, não tenho uma pontuação final

Isso usa o Blum Blum Shub PRNG, por isso deve passar na maioria dos casos. Os números usados ​​são grandes o suficiente, nenhum padrão aparecerá nos 16 MB de casos de teste

Objetivo-C, 40/1 = 40

Abordagem bastante inteligente, explorando .hashpara enganar um pouco aqui, mas eu gosto

for(int v=9;v=@(v).hash;printf("%i",v));