Construye un generador de números aleatorios que pase las pruebas de Diehard

50

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.

Joe Z.
fuente
¿Está permitido el código que requiere conectividad a Internet? (no accederé a ninguna función aleatoria en línea, pero quizás
haga
"Esta función no debe recurrir a ninguna biblioteca u otras funciones que no se hayan escrito también como parte del programa". Eso incluye funciones de conectividad a Internet. Tu generación debe ser puramente algorítmica.
Joe Z.
El paquete intransigente espera archivos de entrada de 10-11 MB.
primo
El enlace a las pruebas parece estar roto, aquí hay una posible alternativa.
2012 Arcampion
¿Cómo debería hacer esto para mi respuesta de ataque cerebral (eliminada a continuación)? Creo que el código es demasiado lento para ser práctico
Christopher

Respuestas:

6

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í.

Campeonato 2012
fuente
28!-67Es algo prohibitivo. ¿Hay un valor más pequeño que cabría en un entero de 64 bits?
primo
@primo Al igual que Python, los enteros de Mathematica son de precisión arbitraria por defecto, por lo que no causa ningún problema.
2012 Arcampion
Estaba pensando específicamente en la portabilidad en C.
primo
@primo gmplib.org
2012 Arcampion
21

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 32 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 32 ( 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 32 ), 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
primo
fuente
Sí, noté que su algoritmo "falló" la prueba de flujo de bits, pero en realidad tenía algunos valores por debajo de 0.999999. Aún así, sus pruebas parecen precisas.
Joe Z.
Sin embargo, hay un problema, y ​​es que los números del 4294951589 al 4294967295 no tienen posibilidad de ocurrir (aunque supongo que eso es parte de la razón por la que fallaron algunas de las pruebas de Diehard).
Joe Z.
1
@JoeZeng sí, eso es un problema. Es más evidente en la Prueba 5: a la primera ejecución le faltan 151 mil palabras, y al resto solo le faltan 143 mil. Una solución sería elegir un módulo un poco más grande que 2 ^ 32, y permitir que los valores que son demasiado grandes para ajustarse a cero, pero no pude encontrar uno que funcione bien. Si lo hago, actualizaré la publicación.
primo
7

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).

Keith Randall
fuente
¿Podría pegar un archivo de registro?
primo
Inicie sesión aquí: codepad.org/ZWhoGe0t
Keith Randall el
1
Estúpido Windows. Estaba convirtiendo todas las ocurrencias de \ry \npara \r\n, lo que obviamente sesga los resultados. Una solución es escribir el archivo directamente usando f = open('file.bin', 'wb')y f.write.
primo
Este nuevo puntaje socava el puntaje anterior, por lo que ahora es la respuesta aceptada.
Joe Z.
Este nuevo puntaje fue socavado una vez más, así que he cambiado la respuesta aceptada.
Joe Z.
4

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
YenTheFirst
fuente
@JoeZ Esta parece ser la nueva respuesta más baja, vinculada con la nueva respuesta de Mathematica.
Riking
3

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();
    }
Andrew P.
fuente
2

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;
    }

}
Ricardo II
fuente
1

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))
Keith Randall
fuente
"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 incorporada de rand () de un lenguaje". Lo siento, pero eso descalifica tu entrada.
Joe Z.
Para ser claros, "len" también descalificaría su entrada.
Joe Z.
¿Dónde se traza la línea? ¿Es +una función incorporada, y por lo tanto descalificada?
Keith Randall el
66
Pero en muchos idiomas, los operadores y las funciones son idénticos. Ver +y __add__en python, o sobrecarga de operadores en c ++. Sé que estoy dividiendo los pelos, así que considera este ejemplo. En python, ¿puedo crear un mapa como este {'a':5}:? Probablemente dirás que sí, pero luego considera que debajo de las sábanas, te hash('a')llaman cuando haces eso.
Keith Randall el
2
Supongo que dibujaría la línea cuando necesite referirse sintácticamente a la función de esa manera. Si puede encontrar un hack en Python que le permita acceder directamente a la dirección del mapa sin referirse sintácticamente a la función "hash", podría aceptarlo.
Joe Z.
1

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.

user1502040
fuente
0

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

Christopher
fuente
si esto no es válido, solo dígame
Christopher
1
Cuento 344. Teorema: ningún programa Brain-flak completamente desarrollado tiene un número impar de bytes.
user202729
0

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));
Albert Renshaw
fuente