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.

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.

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 ³² 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 ³² ( 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 ³² ), 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

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

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

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

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

}

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

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.

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.

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