Inspirado por Random con las manos atadas :

La meta

El objetivo de este desafío es escribir un programa que genere una secuencia de bits pseudoaleatoria, que es una cadena de 1s y 0s que parece ser puramente aleatoria, pero que en realidad se genera de manera determinista. Su programa debe generar una cadena de 1 y 0 (con espacios en blanco opcionales) y debe cumplir los siguientes requisitos:

1. Con tiempo y memoria ilimitados, su programa debe continuar produciendo una cadena de 1s y 0s para siempre
2. Su programa debe generar más de 1000 bits aleatorios en aproximadamente un minuto, en una máquina razonable. Si este requisito es imposible, lo disminuiré.
3. La cadena de bits puede repetirse, pero la longitud de la sección de repetición debe ser superior a 1000 bits.
4. La cadena de bits debe pasar tantas pruebas de aleatoriedad (descritas a continuación) como sea posible.
5. El programa no debe tomar ninguna entrada de ninguna fuente externa ni utilizar ninguna función incorporada de tipo rand ().
6. Debido al requisito anterior, el programa debe generar la misma cadena de bits exacta cada vez que se ejecuta.

Prueba de aleatoriedad # 1

La cadena de bits pseudoaleatorios no debe incluir ningún patrón obvio en la inspección visual.

Prueba de aleatoriedad n. ° 2 (sujeta a cambios según los comentarios)

La cadena de bits debe contener una distribución igual de 1s y 0s. Para probar esto (y otras cosas también), el flujo de bits se divide en segmentos de 3 bits de longitud, como 101|111|001.

De todos estos segmentos, 1/8 de ellos deben tener tres 1s y no 0s, 3/8 de ellos deben tener dos 1s y uno 0, 3/8 de ellos deben tener un 1 y dos 0s, y 1/8 de ellos no deberían tener 1s y tres 0s.

Prueba de aleatoriedad # 3

Una "ejecución" se define como una serie consecutiva de bits que tienen el mismo valor. La cadena 1001001110tiene tres ejecuciones de tamaño 1 ( 1..1.....0), dos ejecuciones de tamaño 2 ( .00.00....) y una ejecución de tamaño 3 ( ......111.). Tenga en cuenta que las ejecuciones no se superponen.

De una cadena de 1000 bits aleatorios, debe haber aproximadamente 250 ejecuciones de tamaño 1, 125 ejecuciones de tamaño 2, 62 ejecuciones de tamaño 3, etc. En general, para 1000/(2**(R+1))ejecuciones de tamaño R, debería haber aproximadamente ejecuciones de ese tamaño.

Prueba de aleatoriedad # 4

Los primeros 840 bits se dividen en dos mitades de 420 bits cada una. Cada bit en la primera mitad se compara con el bit correspondiente en la segunda mitad. Los dos bits deben coincidir aproximadamente el cincuenta por ciento del tiempo.

Aquí está el código fuente de un programa Perl que realiza las pruebas 2 a 4. A partir de ahora, requiere que la cadena de bits no contenga ningún espacio en blanco.

Objetivo Criterio ganador ¡Tiempo!

El ganador es el programa que pasa los 6 requisitos y todas las pruebas de aleatoriedad en la medida en que no se puede distinguir de la aleatoriedad. Si varios programas logran esto, entonces ganará el que demore más tiempo en repetirse. Si varios programas logran esto, entonces podría tener que encontrar más pruebas de aleatoriedad para actuar como desempate.

C, 61

main(s,n){for(n=1u<<31;putchar((s%=n)/(n/2)&1|48);s*=65539);}

Sí, sé que no es código golf. Obviamente, esto es más bien una anti-solución ... pero cumple con sus criterios.

fuera | cabeza -c840
$ ./a.out | cabeza -c840 | perl tester.pl
Prueba 2: 1 (1) 2.93333333333333 (3) 3.1 (3) 0.966666666666667 (1)
Prueba 3: 214 99 71 24 7 5 1 1 2 2
Prueba 4: 0.495238095238095

La duración del período es de 2²⁹.

Mathematica 78 53 caracteres

Los dígitos de la representación binaria de Pi parecen comportarse como si fueran producidos caóticamente, aunque esto no está probado.

La siguiente rutina simple devuelve determinísticamente como una cadena los dígitos binarios de pi, correspondientes a ddígitos decimales:

f[d_]:=ToString@FromDigits@RealDigits[N[Pi,d],2][[1]]

Uso

Si solicitamos la contrapartida de 301 dígitos decimales de Pi, recibimos 1000 dígitos binarios.

f[301]
StringLength[%]

(* out *)
1100100100001111110110101010001000100001011010001100001000110100110001001100011001100010100010111000000011011100000111001101000100101001000000100100111000001000100010100110011111001100011101000000001000001011101111101010011000111011000100111001101100100010010100010100101000001000011110011000111000110100000001001101110111101111100101010001100110110011110011010011101001000011000110110011000000101011000010100110110111110010010111110001010000110111010011111110000100110101011011010110110101010001110000100100010111100100100001011011010101110110011000100101111001111110110001101111010001001100010000101110100110100110001101111110110101101011000010111111111101011100101101101111010000000110101101111110110111101110001110000110101111111011010110101000100110011111101001011010111010011111001001000001000101111100010010110001111111100110010010010010100001100110010100011110110011100100010110110011110111000010000000000111110010111000101000010110001110111111000001011001100011011010010010000011011000011100011

1000 (* characters *)

Como Pi es un número irracional, no hay punto. Sin embargo, habrá restricciones prácticas debido al hardware que se está ejecutando.

Prueba 1 Me parece bien.

Prueba 2

d=301;
Partition[RealDigits[N[Pi,d],2][[1]],{3}];
Tally[%]
(* out *)
{{{1,1,0},35},{{0,1,0},45},{{0,0,0},41},{{1,1,1},40},
{{0,1,1},50},{{1,0,1},32},{{1,0,0},43},{{0,0,1},47}}

Verificación más exhaustiva:

d=10^6;
Partition[RealDigits[N[Pi,d],2][[1]],{3}];
Tally[%]

{{{1,1,0},138565},{{0,1,0},138146},{{0,0,0},138260},{{1,1,1},138427},
{{0,1,1},139119}, {{1,0,1},138404},{{1,0,0},137926},{{0,0,1},138462}}

Prueba 3: carreras

d=10^6;
res3=SortBy[Tally@Split@RealDigits[N[Pi,d],2][[1]],Last]/.{a_,b_}:> {Length[a],b}
ListPlot[res3 ,AxesLabel-> {"Run Length","Runs"},AxesOrigin->{0,0}]

Ejecuté una gran cantidad de casos para verificar sistemáticamente la distribución de las corridas. En aproximadamente 3 millones de dígitos binarios, hubo 830k corridas de 1, 416k corridas de 2, 208k corridas de 3, 104k corridas de 4, etc.

Prueba 4: coincidencia de la primera y segunda mitad de los datos

Los partidos son los 212 casos de 0 y 2; los desajustes son los 208 casos donde la suma de los dígitos respectivos es 1.

d=301;
Tally[Plus@@Partition[Take[RealDigits[N[Pi,d],2][[1]],840],420]]

(* out *)
{{1,208},{0,108},{2,104}}

Sincronización

Se tarda menos de dos segundos en calcular 3321928 dígitos binarios (correspondientes a 10 ^ 6 dígitos decimales).

(r=f[10^6]);//AbsoluteTiming
StringLength[r]

(*out*)
{1.785928,Null}    
3321928

Python, 90

g=[19]
print(''.join("01"[(g.append((11*g[-1]+13)%1024)or g[-1])>512]for i in range(1000)))

ges el valor de la semilla El muestreo aleatorio exhibe una distribución notablemente normal. El muestreo aleatorio repetido de las medias muestrales arrojó una media 0.506y una desviación estándar de .0473(tamaño de muestra de 1000). Desafortunadamente, la aleatoriedad es altamente sensible a la semilla inicial. La semilla en el código anterior me dio la mejor aleatoriedad: p

ACTUALIZAR

Veamos cómo este código resiste las pruebas del OP:

Prueba n. ° 1

Este es un poco subjetivo ... pero me parece bastante irregular.

Prueba n. ° 2

Tres 1: 0.141
Dos 1: 0.371
Uno 1: 0.353
Cero 1: 0.135

Prueba n. ° 3

Se ejecuta por tamaño:

8: 11
7: 3
6: 7
5: 13
4: 32
3: 67
2: 119
1: 216

Prueba n. ° 4

Ratio de igualdades: 0.94 Esto es un error tipográfico. Se actualizará con el número correcto pronto.

Haskell 74 58

main=print$iterate(read.take 9.show.(^3))7>>=show.(`mod`2)

Gracias a shiona por la simplificación. Resultados:

/ pseudoaleatorio | cabeza -c 1000

./pseudorandom | cabeza -c 1000 | perl test.pl

Prueba 2: 0.966666666666667 (1) 2.4 (3) 3.3 (3) 1.33333333333333 (1)

Prueba 3: 260108 66 33 15 11 5 2

Prueba 4: 0.495238095238095

Este también es un terrible generador pseudoaleatorio (similar al utilizado por von-Neuman). Para aquellos que no estaban al tanto concatMap == (=<<) == flip . (>>=)(para listas)

La pregunta es esencialmente equivalente a "implementar un cifrado de flujo". Así que implemento RC4, ya que es relativamente simple.

No uso ninguna clave y dejo caer los primeros 100000 bits, porque el comienzo de RC4 está un poco sesgado, especialmente porque omití la programación de claves. Pero espero que pase tu prueba incluso sin eso (ahorrando 20 caracteres de código).

Normalmente, se generaría un byte completo por ciclo, pero la conversión a binario es bastante fea en C #, por lo que simplemente descarto todo excepto el bit menos significativo.

var s=Enumerable.Range(0,256).ToArray();
byte i=0,j=0;
for(int k=0;;k++)
{
    i++;
    j+=(byte)s[i];
    var t=s[i];s[i]=s[j];s[j]=t;
    if(k>99999)
        Console.Write(s[i]+s[j]&1);
}

O sin espacios:

var s=Enumerable.Range(0,256).ToArray();byte i=0,j=0;for(int k=0;;k++){i++;j+=(byte)s[i];var t=s[i];s[i]=s[j];s[j]=t;if(k>99999)Console.Write(s[i]+s[j]&1);}

C #, 156 caracteres, funciona en el modo de declaración de LinqPad. Para un programa completo de C #, agregue la repetitiva habitual.

También podríamos usar cripto primitivas integradas (solución Cheater):

var h=SHA256.Create();for(BigInteger i=0;;i++){Console.Write(h.ComputeHash(i.ToByteArray())[0]%2);}

(C #, 99 caracteres, funciona en el modo de declaración de LinqPad. Para el compilador normal de C # necesitará agregar un poco de repetitivo)

La salida de las funciones criptográficas de hash está diseñada para ser indistinguible de los datos aleatorios, por lo que espero que pase todas las pruebas de aleatoriedad (morir más duro ...), pero soy demasiado vago para probar.

C, 52 caracteres

main(a){for(a=1;putchar(48+a%2);a=a/2^-(a%2)&576);}

Este es un LFSR de 10 bits, resultados de la prueba:

$ ./a.out |head -c 1000 | perl randtest.pl
Test 2: 1.13333333333333 (1) 2.86666666666667 (3) 3.16666666666667 (3) 0.833333333333333 (1)
Test 3:  251 122 64 32 16 8 4 2  1
Test 4: 0.466666666666667

Sabio / Python

Este programa imprime los dígitos binarios más a la derecha que son comunes a todas las torres de exponenciación suficientemente altas de forma 3 ^{3 3 3 . .} . Por todo lo que podría generarse de manera factible, estos son los dígitos binarios más a la derecha del número de Graham . La secuencia de dígitos es infinita y no es periódica.

m = 1; x = 3; last = 0
while True:
    m *= 2; x = pow(3,x,m); l = len(bin(x))
    print '1' if l > last else '0',
    last = l

Para 1000 dígitos, esto tomó menos de 2 segundos; sin embargo, el tiempo aumentará mucho más rápido que linealmente en el número de dígitos.

Los resultados de la prueba usando el programa OP son

Test 2: 1.26666666666667 (1) 3.16666666666667 (3) 2.8 (3) 0.766666666666667 (1)
Test 3:  268 126 61 30 20 7 2  1 1
Test 4: 0.466666666666667

(Consulte ¿Son aleatorios los dígitos más a la derecha de G? Para más de 32000 dígitos y pruebas estadísticas adicionales).

Java, 371 317

Basado en un LFSR de 128 bits (las derivaciones de bits provienen de la nota 52 de la aplicación xilinx )

EDITAR: no estaba satisfecho con el uso de BigInteger, por lo que esta versión no. Guardado algunos personajes. La producción puede ser un poco menos aleatoria ya que no podría pensar en un buen método de 'siembra'.

Nuevo Código: Argumentos: BITS_TO_PRINT

class R{public static void main(String[]a){int L=65536;int[]v={0,128,126,101,99};int[]b=new int[L];for(int x=0;x<L;x++)b[x]=(x*x)&1;for(int i=0;i<Integer.parseInt(a[0])+L;i++){if(1!=(b[v[1]]^b[v[2]]^b[v[3]]^b[v[4]]))b[v[0]]=1;else b[v[0]]=0;if(i>L)System.out.print(b[v[0]]);for(int j=0;j<5;j++)v[j]=(v[j]-1)&(L-1);}}}

Versión antigua: Argumentos: SEED, BITS_TO_PRINT

import java.math.BigInteger;class R{public static void main(String[]a){BigInteger v=new BigInteger(a[0]);BigInteger m=new BigInteger("ffffffffffffffffffffffffffffffff",16);for(int i=Integer.parseInt(a[1]);i>0;i--){v=v.shiftLeft(1);if(!(v.testBit(128)^v.testBit(126)^v.testBit(101)^v.testBit(99))){v=v.setBit(0);}v=v.and(m);java.lang.System.out.print(v.testBit(0)?1:0);}}}

Nueva versión: Ejemplo de salida, bits = 100:

011001100111000110010100100111011100100111000111001111110110001001100000100111111010111001100100011

JavaScript: 1ms a 2ms para 1000 bits pseudoaleatorios (139ms a 153ms para 100000 bits)

Esta solución utiliza el hecho de que las raíces cuadradas son irracionales y, por lo tanto, bastante aleatorias. Básicamente, toma la raíz cuadrada de 2 para comenzar, la convierte en binaria, tira la parte principal que coincide con la raíz anterior, la agrega a la cadena aleatoria, se repite con el siguiente número más alto (o vuelve a 2 si el número se repite) y tenía al menos 30 bits de longitud), y devuelve la cadena aleatoria una vez que es lo suficientemente larga.

var getDeterministicPseudoRandString = function(length){
    var randString = '';

    var i = 2;
    var prevRand = '';

    outerLoop:
    while(randString.length < length){
        var nextRand, nextFullRand = Math.sqrt(i++).toString(2).substring(1).replace('.', '');
        nextRand = nextFullRand;
        for(var j = prevRand.length; j > 0; j--){
            var replaceString = prevRand.substring(0, j);

            nextRand = nextFullRand;

            if(nextFullRand.indexOf(replaceString) == 0){
                if(j == prevRand.length && j > 30){
                    //start i over at 2
                    console.log('max i reached: ' + i);

                    i = 2;
                    continue outerLoop;
                } else {
                    nextRand = nextFullRand.replace(replaceString, '');
                }

                break;
            }
        }
        prevRand = nextFullRand;

        randString += nextRand;
    }

    return randString.substring(0, length);//Return the substring with the appropriate length
};

Todavía no lo he pasado por las pruebas, pero imagino que les irá bien. Aquí hay un violín para que puedas verlo en acción. Para mis tiempos, simplemente ejecuté el programa varias veces y tomé los valores más rápidos y más lentos como rangos.

Pitón

import hashlib
x=''
while 1:
    h=hashlib.sha512()
    h.update(x)
    x=h.digest()
    print ord(x[0])%2

Debería tener un período de aproximadamente 2 ^ 512.

perl, 44 bytes

Sé que esto no es golf de código, pero siempre he sido fanático de tomar los bits de orden inferior de una función cuadrática simple, por ejemplo:

$x=1/7;print substr($x*=4-4*$x,9,1)%2while 1

El período es más largo que 3 mil millones, pero me he quedado sin espacio en disco para calcular más.