Construire un générateur de nombres aléatoires qui passe les tests de Diehard

50

Bien qu'il y ait beaucoup de questions de code de golf impliquant ici le hasard, je n'en ai pas encore vu qui demande la construction d'un générateur algorithmique de nombres pseudo-aléatoires. Il y a celui-ci qui vous demande de générer un flux de bits, mais les tests aléatoires fournis sur celui-ci n'étaient pas très rigoureux, et ce n'est pas du code-golf.

Le programme que vous écrivez aura une seule fonction appelable qui retournera un entier aléatoire compris entre 0 et 4294967295. Cette fonction ne doit pas faire appel à des bibliothèques ou à d'autres fonctions qui n'étaient pas également écrites dans le programme, en particulier les appels à / dev / random. ou la bibliothèque intégrée rand () d'une langue. Plus spécifiquement, vous êtes limité aux opérateurs de base de la langue dans laquelle vous travaillez, tels que les instructions arithmétiques, d'accès aux tableaux et de contrôle de flux conditionnel.

Le score de votre programme est calculé comme suit:

Score = C / R

Où C est la longueur du code en caractères et R le nombre de tests de Diehard réussis par votre générateur (si votre générateur de nombres aléatoires ne réussit pas au moins un test de Diehard, son score est infini et il est disqualifié). Votre générateur passe un test de Diehard si le fichier qu'il génère fournit une plage de valeurs P qui semblent être distribuées uniformément sur l'intervalle [0, 1).

Pour calculer R, utilisez votre générateur de nombre aléatoire avec sa valeur de départ par défaut pour générer un fichier de données binaires de 16 Mo. Chaque appel de la fonction renvoie quatre octets; si votre fonction est trop lente pour restituer des octets, vous devrez trouver un compromis pour obtenir un score faible en fonction de la difficulté de le tester. Ensuite, exécutez-le dans les tests de Diehard et vérifiez les P-valeurs fournies. (N'essayez pas de les mettre en œuvre vous-même; utilisez ceux fournis ici )

Le score le plus bas gagne, bien sûr.

Joe Z.
la source
Le code nécessitant une connexion Internet est-il autorisé? (Je ne vais pas accéder à une fonction aléatoire en ligne, mais peut-être au ping ou aux valeurs d'un appel d'api)
elssar
"Cette fonction ne doit faire appel à aucune bibliothèque ou autre fonction qui n’a pas été écrite dans le cadre du programme." Cela inclut les fonctions de connectivité Internet. Votre génération devrait être purement algorithmique.
Joe Z.
La suite inflexible attend des fichiers d’entrée de 10 à 11 Mo.
Primo
Le lien vers les tests semble être rompu, voici une alternative possible.
2012rcampion
Comment cela devrait-il fonctionner pour ma réponse cerveau-flak (supprimée ci-dessous)? Je pense que le code est trop lent pour être pratique
Christopher

Réponses:

6

Mathematica, 32/15 = 2.133

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

Une implémentation simple de BBS .

Fichier binaire généré avec:

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

Résumé des résultats:

 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

Complet random.binici.

Fichier journal complet ici.

2012rcampion
la source
28!-67est un peu prohibitif. Y a-t-il une valeur plus petite qui tiendrait dans un entier de 64 bits?
Primo
@primo Comme Python, les entiers de Mathematica ont une précision arbitraire par défaut. Par conséquent, cela ne pose pas de problème.
2012rcampion
Je pensais spécifiquement à la transférabilité en C
primo le
@primo gmplib.org
2012rcampion le
21

Perl 28/13 ≈ 2,15

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

journal ici

Perl 29/13 ≈ 2.23

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

journal ici

Il s’agit d’une variante du Xorshift , qui utilise une division en virgule flottante au lieu d’un décalage à droite. Ils ont tous deux réussi 13 des 15 tests, échouant seulement aux tests 6 et 7.

Je ne sais pas exactement combien de temps le cycle est, mais comme le code suivant ne se termine pas dans un court laps de temps, il est probable que le code 2 32 complet :

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

Perl 39/10 = 3,9

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

Remarque: si vous recherchez un PRNG Blum-Blum-Shub-esque, la solution de Keith Randall est bien meilleure que l’un ou l’autre.

Comme pour ma solution originale ci-dessous, il s'agit également d'une implémentation du Blum Blum Shub, avec une différence majeure. J'utilise un module légèrement supérieur à 2 32 ( M = 50971 • 84263 ), et chaque fois qu'une valeur est rencontrée qu'il ne s'agit pas d'un entier 32 bits valide (supérieur à 2 32 ), il renvoie la valeur suivante dans le champ. rotation à la place. En substance, ces valeurs sont élaguées, laissant le reste de la rotation non perturbé, ce qui permet une distribution presque uniforme.

Cela semble avoir aidé. En plus de réussir les mêmes 9 tests qu'auparavant, il passe également le test Distance minimale de manière convaincante. Vous trouverez un exemple de fichier journal ici .


Perl 33/9 ≈ 3,67 (invalide?)

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

Remarque: cette solution peut être considérée comme non valide car les 0,00037% supérieurs de la plage ne seront jamais observés.

Une mise en œuvre rapide et sale du Blum Blum Shub . Je réclame les résultats suivants:

 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

Vous trouverez un exemple de fichier journal ici . N'hésitez pas à contester les résultats. Le fichier pour diehard peut être généré de la manière suivante:

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

puis canaliser la sortie dans un fichier. La Distance minimale semble avoir été dépassée, mais si vous l'exécutez plusieurs fois, elle est toujours très proche de 1,0 , ce qui indique un échec.


Détails

En général, le Blum Blum Shub est un PRNG terrible, mais ses performances peuvent être améliorées en choisissant un bon module. Le M que j'ai choisi est 7027 • 611207 . Les deux facteurs premiers, p et q , ont un résidu modulaire 3 (mod 4) et gcd ((p-1), φ (q-1)) = 2 , ce qui est aussi faible que possible.

Bien que ce soient les seuls critères listés sur la page du wiki, cela ne semble pas être suffisant. Presque tout le modulo que j'ai essayé a échoué à tous les tests. Mais il y en a une poignée qui va passer certains des tests, et celui que j'ai choisi semble être exceptionnellement bon, peu importe la raison.

En conclusion, le test 5 semble à lui seul être un assez bon indicateur de la qualité du PRNG. S'il ne passe presque pas le test 5, les autres échoueront de manière spectaculaire.


BONUS: Perl 62/14 4.43

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

Juste pour geekery, il s'agit d'une version 32 bits du PRNG utilisée dans le Tetris d'origine pour NES. Étonnamment, il passe 14 des 15 tests!

 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

Exemple de fichier journal peut avant ici .

Certes, le 1..37bit n'est pas une transcription exacte. Dans la version originale, la routine d'entropie est mise à jour 60 fois par seconde, puis interrogée à intervalles aléatoires, en grande partie en fonction des entrées de l'utilisateur. Pour ceux qui souhaitent démonter la ROM, la routine d'entropie commence à 0xAB47.

Pseudo-code de style 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
la source
Oui, j'ai remarqué que votre algorithme avait "échoué" lors du test du flux binaire, mais qu'il avait en réalité quelques valeurs inférieures à 0,999999. Pourtant, vos tests semblent précis.
Joe Z.
Il y a cependant un problème, à savoir que les chiffres compris entre 4294951589 et 4294967295 n'ont aucune chance de se produire (même si je suppose que c'est en partie la raison pour laquelle certains des tests de Diehard ont échoué).
Joe Z.
1
@ JoeZeng oui, c'est un problème. C'est le cas le plus évident dans le test 5: la première manche contient 151k mots manquants et le reste d'entre eux ne manque que 143k. Une solution serait de choisir un module légèrement supérieur à 2 ^ 32 et de laisser les valeurs trop grandes trop lentes, mais je n’ai pas pu en trouver un qui fonctionne bien. Si je le fais, je mettrai à jour le post.
Primo
7

Python, 46/15 = 3,0666

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

Utilise l’exponentiation modulaire pour générer de l’aléatoire. 2 ** 32-5 est le plus grand nombre premier inférieur à 2 ^ 32. (Même problème avec l'impossibilité de lancer le test n ° 2.)

Keith Randall
la source
Pourriez-vous coller un fichier journal?
Primo
Connectez-vous ici: codepad.org/ZWhoGe0t
Keith Randall
1
Windows stupide. Il convertissait toutes les occurrences de \ret \nen \r\n, ce qui fausse évidemment les résultats. Un correctif consiste à écrire le fichier directement en utilisant f = open('file.bin', 'wb')et f.write.
primo
Ce nouveau score réduit le score précédent, il en va de même pour la réponse acceptée.
Joe Z.
Ce nouveau score a encore été réduit, alors j'ai changé la réponse acceptée.
Joe Z.
4

Ruby, 32/15 = 2.1333

C'est la solution de Keith Randall, implémentée en Ruby.

$v=3;def R;$v=$v**3%(2**32-5)end
YenTheFirst
la source
@JoeZ Cela semble être la nouvelle réponse la plus basse, à égalité avec la toute nouvelle réponse 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);}

Cela a réussi tous les tests.

Avec pas trop de caractères, il passe TestU01.

Résultat: 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.
la source
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;}

Résultats

Réussite à tous sauf au test n ° 6
Voir les résultats à l' adresse http://codepad.org/k1NSoyQW

Explication

C # ne peut tout simplement pas rivaliser avec Ruby et Python pour la concision, comme d'habitude, mais j'ai aimé essayer. Il existe certainement d'autres valeurs qui fonctionneront tout aussi bien (à savoir, la valeur initiale pour j = 999 et le diviseur = 277). Je les ai choisis après une brève expérimentation.

Avec wrapper de création de fichier

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

}
Richard II
la source
1

Python, 41/15 = 2,73333

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

Un peu comme tricherie en utilisant la fonction de hachage intégrée, mais elle est intégrée, donc pas plus de tricherie que d’utiliser d’autres fonctions intégrées, comme len. D'un autre côté, cela me fait mal de devoir payer pour la global v;déclaration ...

Réussit tous les tests de Diehard (j'ai eu un problème avec le test n ° 2, il se SEGV sur mon ordinateur OSX. Pour mon score, je suppose qu'il passera).

Voici un pilote pour générer le fichier de 16 Mo:

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
la source
"Cette fonction ne doit faire appel à aucune bibliothèque ni à aucune autre fonction non également écrite dans le cadre du programme, en particulier les appels à / dev / random ou à la bibliothèque rand () intégrée à un langage." Je suis désolé, mais cela disqualifie votre participation.
Joe Z.
Pour être clair, "len" disqualifierait également votre participation.
Joe Z.
Où tracez-vous la ligne? Une +fonction intégrée est-elle, et donc disqualifiée?
Keith Randall
6
Mais dans beaucoup de langues, les opérateurs et les fonctions sont identiques. Voir +et __add__en python, ou la surcharge des opérateurs en c ++. Je sais que je suis un peu en train de couper les cheveux en quatre, alors prenons cet exemple. En python, puis-je créer une carte comme celle-ci {'a':5}:? Vous allez probablement dire oui, mais considérez ensuite que sous la couverture, hash('a')on vous appelle quand vous le faites.
Keith Randall
2
Je suppose que je tracerais la ligne lorsque vous aurez besoin de faire référence syntaxiquement à la fonction de cette façon. Si vous pouvez trouver un hack en Python qui vous permettra d’accéder directement à l’adresse de la carte sans faire référence syntaxiquement à la fonction "hash", je pourrais l’accepter.
Joe Z.
1

C, 38/15 = 2,533

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

Je ne pouvais pas faire fonctionner les tests Diehard sur ma machine, mais celle-ci réussit jusqu'à 8 Go de sortie de la suite PractRand, donc je suppose que cela les réussirait tous.

utilisateur1502040
la source
0

Brain-Flak , 344 / (en attente)

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

Essayez-le en ligne!

Cela fonctionne très bien, mais les liens des tests inflexibles sont tous brisés :( jusqu'à ce que nous en obtenions de nouveaux, je n'ai pas de score final.

Cela utilise le PRNG Blum Blum Shub, il devrait donc passer la plupart des cas. Les nombres utilisés sont assez grands, aucun motif n'apparaîtra dans les 16 Mo de cas de test.

Christopher
la source
si cela est invalide, dites-le moi
Christopher
1
J'en compte 344. Théorème: Aucun programme Brain-Flak entièrement joué au golf n'a un nombre impair d'octets.
user202729
0

Objectif-C, 40/1 = 40

Approche assez intelligente, exploitant .hashpour tricher un peu ici, mais j'aime bien

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