Si bien hay muchas preguntas de código de golf aquí que involucran aleatoriedad, aún no he visto una que realmente solicite la construcción de un generador algorítmico de números pseudoaleatorios. Hay una que le pide que genere una secuencia de bits, pero las pruebas de aleatoriedad proporcionadas en esa no fueron muy rigurosas, y no es código de golf.

El programa que escriba tendrá una única función invocable que devolverá un entero aleatorio de 0 a 4294967295. Esta función no debe invocar ninguna biblioteca u otras funciones que no se hayan escrito también como parte del programa, especialmente las llamadas a / dev / random o la biblioteca rand () incorporada en un idioma. Más específicamente, está limitado a los operadores básicos del lenguaje en el que está trabajando, como la aritmética, el acceso a la matriz y las declaraciones de control de flujo condicional.

La puntuación de su programa se calcula de la siguiente manera:

Score = C / R

Donde C es la longitud del código en caracteres, y R es el número de pruebas Diehard que su generador pasa (si su generador de números aleatorios no pasa al menos una prueba Diehard, su puntaje es infinito y está descalificado). Su generador pasa una prueba Diehard si el archivo que genera proporciona un rango de valores P que parecen estar distribuidos uniformemente a lo largo del intervalo [0, 1).

Para calcular R, use su generador de números aleatorios con su semilla predeterminada para generar un archivo de datos binarios de 16 MB. Cada llamada de la función devuelve cuatro bytes; Si su función es demasiado lenta para devolver bytes, esto supondrá una compensación para lograr un puntaje bajo por lo difícil que es probar. Luego, ejecútelo a través de las pruebas Diehard y verifique los valores P proporcionados. (No intente implementarlos usted mismo; use los que se proporcionan aquí )

La puntuación más baja gana, por supuesto.

Mathematica, 32/15 = 2.133

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

Una implementación sencilla de BBS .

Archivo binario generado con:

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

Resumen de 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

Lleno random.binaquí

Archivo de registro completo aquí.

Perl 28/13 ≈ 2.15

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

archivo de registro aquí

Perl 29/13 ≈ 2.23

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

archivo de registro aquí

Estos son una especie de variación en un Xorshift , utilizando la división de punto flotante en lugar de un desplazamiento a la derecha. Ambos pasan 13 de 15 pruebas, fallando solo las pruebas 6 y 7.

No estoy exactamente seguro de cuánto dura el ciclo, pero debido a que el siguiente código no termina en un período corto de tiempo, es probable que sea el 2 ³² completo :

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

Perl 39/10 = 3.9

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

Nota: si está buscando un PRNG Blum-Blum-Shub-esque, la solución de Keith Randall es mucho mejor que cualquiera de estos.

Al igual que con mi solución original a continuación, esta también es una implementación de Blum Blum Shub, con una gran diferencia. Utilizo un módulo ligeramente mayor que 2 ³² ( M = 50971 • 84263 ), y cada vez que se encuentra un valor que no es un entero de 32 bits válido (es decir, mayor que 2 ³² ), devuelve el siguiente valor en el rotación en su lugar. En esencia, estos valores se eliminan, dejando el resto de la rotación sin perturbaciones, lo que resulta en una distribución casi uniforme.

Parece haber ayudado. Además de pasar las mismas 9 pruebas que antes, ahora también pasa convincentemente la prueba de Distancia mínima. Puede encontrar un archivo de registro de muestra aquí .

Perl 33/9 ≈ 3.67 (¿No válido?)

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

Nota: esta solución puede considerarse inválida, ya que nunca se observará el 0,00037% superior del rango.

Una implementación rápida y sucia del Blum Blum Shub . Reclamo los siguientes 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

Puede encontrar un archivo de registro de muestra aquí , no dude en disputar cualquiera de los resultados. El archivo para diehard se puede generar de la siguiente manera:

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

y luego canalizando la salida en un archivo. Parece que la distancia mínima puede haber pasado, pero si la ejecuta varias veces, siempre está muy cerca de 1.0 , lo que indica un error.

Detalles

En general, el Blum Blum Shub es un PRNG terrible, pero su rendimiento se puede mejorar eligiendo un buen módulo. La M que he elegido es 7027 • 611207 . Ambos factores primos, p y q , tienen un residuo modular 3 (mod 4) y mcd (φ (p-1), φ (q-1)) = 2 , que es lo más bajo posible.

Aunque estos son los únicos criterios enumerados en la página wiki, no parece ser suficiente. Casi todo el módulo que probé falló en cada prueba. Pero hay un puñado que pasará algunas de las pruebas, y la que he elegido parece ser excepcionalmente buena, por cualquier razón.

Como nota final, la Prueba 5 por sí sola parece ser un indicador bastante bueno de lo bueno que es el PRNG. Si casi no pasa la Prueba 5, fallará al resto espectacularmente.

BONIFICACIÓN: Perl 62/14 ≈ 4.43

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

Solo por geekery, esta es una versión de 32 bits del PRNG utilizada en el Tetris original para NES. Sorprendentemente, ¡pasa 14 de las 15 pruebas!

 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

Ejemplo de archivo de registro puede antes aquí .

Es cierto que el 1..37bit no es una transcripción exacta. En la versión original, la rutina de entropía se actualiza 60 veces por segundo y luego se consulta a intervalos aleatorios, dependiendo en gran medida de la entrada del usuario. Para cualquiera que se preocupe por desmontar la ROM, la rutina de entropía comienza en 0xAB47.

Seudocódigo de 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

Utiliza exponenciación modular para generar aleatoriedad. 2 ** 32-5 es el primo más grande menor que 2 ^ 32. (El mismo trato con no poder ejecutar la prueba # 2).

Rubí, 32/15 = 2.1333

Esta es la solución de Keith Randall, implementada en 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);}

Esto pasó todas las pruebas.

Con no demasiados caracteres más, pasa 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

Pasa todos excepto la prueba # 6
Vea los resultados en http://codepad.org/k1NSoyQW

Explicación

C # simplemente no puede competir con Ruby y Python por la brevedad, como de costumbre, pero disfruté intentarlo. Ciertamente, hay otros valores que funcionarán igual de bien (es decir, el valor inicial para j = 999 y el divisor = 277). Elegí estos después de una breve experimentación.

Con contenedor de creación de archivos

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

Un poco de trampa usando la función hash incorporada, pero está integrada, por lo que no hay más trampa que usar otras incorporadas, como len. Por otro lado, me duele tener que pagar la global v;declaración ...

Pasa todas las pruebas de Diehard (tuve un problema con la prueba # 2, es SEGV en mi máquina OSX. Para mi puntaje, supongo que pasará).

Aquí hay un controlador para generar el archivo 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;}

No pude hacer que las pruebas Diehard funcionaran en mi máquina, pero pasa la suite PractRand por hasta 8 GB de salida, así que supongo que las pasaría a todas.

Brain-Flak , 344 / (pendiente)

<>((()()){})<> 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

Pruébalo en línea!

Esto funciona bien, pero los enlaces de las pruebas intransigentes están rotos :( así que hasta que obtengamos nuevos no tengo una puntuación final

Esto usa el Blum Blum Shub PRNG, por lo que debería pasar la mayoría de los casos. Los números utilizados son lo suficientemente grandes, no aparecerán patrones dentro de los 16 MB de casos de prueba

Objetivo-C, 40/1 = 40

Enfoque bastante inteligente, explotando .hashpara hacer trampa aquí, pero me gusta

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