Inspiré par Random avec les mains liées :
Le but
Le but de ce défi est d'écrire un programme qui génère un flux binaire pseudo-aléatoire, qui est une chaîne de 1 et de 0 qui semble être purement aléatoire, mais qui est en fait généré de manière déterministe. Votre programme doit générer une chaîne de 1 et 0 (avec des espaces en option) et doit répondre aux exigences suivantes:
- Étant donné le temps et la mémoire illimités, votre programme doit continuer à produire une chaîne de 1 et de 0 pour toujours
- Votre programme doit produire plus de 1000 bits aléatoires en une minute environ, sur une machine raisonnable. Si cette exigence est impossible, je la diminuerai.
- La chaîne de bits peut se répéter, mais la longueur de la section extensible doit être supérieure à 1 000 bits.
- La chaîne de bits doit réussir autant de tests d'aléatoire (décrits ci-dessous) que possible.
- Le programme ne doit prendre aucune entrée d'aucune source externe ni utiliser aucune fonction de type rand () intégrée.
- En raison de l'exigence ci-dessus, le programme doit générer la même chaîne de bits exacte à chaque exécution.
Test de hasard # 1
La chaîne de bits pseudo-aléatoires ne doit pas inclure de motif évident lors de l'inspection visuelle.
Test de hasard # 2 (sujet à changement en fonction des commentaires)
La chaîne de bits doit contenir une distribution égale de 1 et de 0. Pour tester cela (et d'autres choses aussi), le flux de bits est divisé en segments de 3 bits, tels que 101|111|001
.
De tous ces segments, 1/8 d'entre eux devraient avoir trois 1 et aucun 0, 3/8 d'entre eux devraient avoir deux 1 et un 0, 3/8 d'entre eux devraient avoir un 1 et deux 0 et 1/8 d'entre eux ne devraient pas avoir de 1 et trois 0.
Test de hasard # 3
Une «exécution» est définie comme une série consécutive de bits qui ont tous la même valeur. La chaîne 1001001110
a trois exécutions de taille 1 ( 1..1.....0
), deux exécutions de taille 2 ( .00.00....
) et une exécution de taille 3 ( ......111.
). Notez que les exécutions ne se chevauchent pas.
Sur une chaîne de 1000 bits aléatoires, il devrait y avoir environ 250 exécutions de taille 1, 125 exécutions de taille 2, 62 exécutions de taille 3, etc. En général, pour la taille d'exécution R, il devrait y avoir environ des 1000/(2**(R+1))
exécutions de cette taille.
Test de hasard # 4
Les 840 premiers bits sont divisés en deux moitiés de 420 bits chacune. Chaque bit de la première moitié est comparé au bit correspondant de la seconde moitié. Les deux bits doivent correspondre à environ cinquante pour cent du temps.
Voici le code source d'un programme Perl qui effectue les tests 2 à 4. Pour l'instant, il requiert que la chaîne de bits ne contienne aucun espace.
Temps de critère de gain objectif!
Le gagnant est le programme qui réussit toutes les 6 exigences et tous les tests de hasard dans la mesure où il est impossible de le distinguer du hasard. Si plusieurs programmes accomplissent cela, alors celui qui prend le plus de temps à répéter gagnera. Si plusieurs programmes accomplissent cela, je devrai peut-être trouver plus de tests d'aléatoire pour agir en tant que bris d'égalité.
la source
Réponses:
C, 61
Ouais, je sais que ce n'est pas du golf de code. C'est évidemment plutôt une anti-solution ... mais elle remplit bien sûr vos critères.
La durée de la période est de 2²⁹.
la source
Mathematica
7853 caractèresLes chiffres de la représentation binaire de Pi semblent se comporter comme s'ils étaient produits de manière chaotique, bien que cela ne soit pas prouvé.
La routine simple suivante retourne de manière déterministe sous forme de chaîne les chiffres binaires de pi, correspondant aux
d
chiffres décimaux:Usage
Si nous demandons l'équivalent de 301 chiffres décimaux de Pi, nous recevons 1000 chiffres binaires.
Parce que Pi est un nombre irrationnel, il n'y a pas de point. Cependant, il y aura des contraintes pratiques en raison du matériel utilisé.
Test 1 me semble bien.
Test 2
Vérification plus approfondie:
Test 3: exécutions
J'ai exécuté un grand nombre de cas pour vérifier systématiquement la distribution des runs. En environ 3 millions de chiffres binaires, il y a eu 830 000 exécutions de 1, 416 000 exécutions de 2, 208 000 exécutions de 3, 104 000 exécutions de 4, etc.
Test 4: Correspondance de la première et de la seconde moitié des données
Les correspondances sont les 212 cas de 0 et 2; les disparités correspondent aux 208 cas où la somme des chiffres respectifs est 1.
Horaire
Il faut moins de deux secondes pour calculer 3321928 chiffres binaires (correspondant à 10 ^ 6 chiffres décimaux).
la source
e
au lieu d'pi
enregistrer un octet?e
distribué de manière chaotique?Python, 90
g
est la valeur de départ. L'échantillonnage aléatoire présente une distribution remarquablement normale. L'échantillonnage aléatoire répété des moyennes de l'échantillon a donné une moyenne0.506
et un écart-type de.0473
(taille de l'échantillon de 1 000). Malheureusement, le caractère aléatoire est très sensible à la semence initiale. La graine dans le code ci-dessus m'a donné le meilleur caractère aléatoire: pMISE À JOUR
Voyons comment ce code résiste aux tests de l'OP:
Test n ° 1
Celui-ci est un peu subjectif ... mais il me semble assez irrégulier.
Test n ° 2
Test n ° 3
Fonctionne par taille:
Test n ° 4
la source
Haskell
7458Merci à shiona pour la simplification. Résultats:
C'est aussi un terrible générateur pseudo-aléatoire (similaire à celui utilisé par von-Neuman). Pour ceux qui n'étaient pas au courant
concatMap == (=<<) == flip . (>>=)
(pour les listes)la source
\x->if odd x then"1"else"0"
parshow.(`mod`2)
.La question est essentiellement équivalente à "implémenter un chiffrement de flux". J'implémente donc RC4, car c'est relativement simple.
Je n'utilise aucune clé et je laisse tomber les 100 000 premiers bits, car le début de RC4 est un peu biaisé, d'autant plus que j'ai sauté la programmation des clés. Mais je m'attendrais à ce qu'il passe votre test même sans cela (sauvegarde de 20 caractères de code).
Normalement, on produirait un octet complet par cycle, mais la conversion en binaire est plutôt moche en C #, donc je rejette simplement tout sauf le bit le moins significatif.
Ou sans espaces:
C #, 156 caractères, fonctionne en mode déclaration de LinqPad. Pour un programme C # complet, ajoutez le passe-partout habituel.
Nous pourrions également utiliser des primitives cryptographiques intégrées (solution de tricheur):
(C #, 99 caractères, fonctionne en mode instruction de LinqPad. Pour le compilateur C # normal, vous devrez ajouter un peu de passe-partout)
La sortie des fonctions de hachage cryptographiques est conçue pour être impossible à distinguer des données aléatoires, donc je m'attends à ce qu'elle passe tous les tests d'aléatoire (mourir plus fort, ...) que vous lui lancez, mais je suis trop paresseux pour tester.
la source
C, 52 caractères
Il s'agit d'un LFSR 10 bits, résultats des tests:
la source
a
devrait commencer comme 1, (en supposant qu'il est appelé sans arguments). Vous pouvez également coller lea=
au milieu, quelque chose commea=a/2^-!putchar(49-a%2)%576
(prendre quelques libertés avec l'algorithme)a
, je l'ai changé à cause de "The program must not take any input from any external sources
"Sage / Python
Ce programme imprime les chiffres binaires les plus à droite qui sont communs à chaque tour d'exponentiation suffisamment haute de la forme 3 3 3 3 . . . Pour tout ce qui pourrait jamais être généré, ce sont les chiffres binaires les plus à droite du nombre de Graham . La séquence de chiffres est infinie et n'est pas périodique.
Pour 1000 chiffres, cela a pris moins de 2 secondes; cependant, le temps augmentera beaucoup plus rapidement que linéairement le nombre de chiffres.
Les résultats des tests utilisant le programme OP sont
(Voir Les chiffres de G les plus à droite sont-ils aléatoires? Pour plus de 32 000 chiffres et des tests statistiques supplémentaires.)
la source
Java,
371317Basé sur un LFSR 128 bits (les taps de bits proviennent de la note 52 de l'application xilinx )
EDIT: Je n'étais pas satisfait d'utiliser BigInteger, donc cette version ne fonctionne pas. Enregistré quelques caractères. La sortie pourrait être un peu moins aléatoire car je ne pouvais pas penser à une bonne méthode de «semis».
Nouveau code: Arguments: BITS_TO_PRINT
Ancienne version: Arguments: SEED, BITS_TO_PRINT
Nouvelle version: exemple de sortie, bits = 100:
la source
JavaScript - 1 ms à 2 ms pour 1000 bits pseudo-aléatoires (139 ms à 153 ms pour 100 000 bits)
Cette solution utilise le fait que les racines carrées sont irrationnelles et donc assez aléatoires. Fondamentalement, il prend la racine carrée de 2 pour commencer, la convertit en binaire, jette la partie principale qui correspond à la racine précédente, ajoute cela à la chaîne aléatoire, répète avec le nombre supérieur suivant (ou revient à 2 si le nombre répété et avait au moins 30 bits de long), et renvoie la chaîne aléatoire une fois qu'elle est suffisamment longue.
Je ne l'ai pas encore parcouru les tests, mais j'imagine que cela leur conviendra. Voici un violon pour que vous puissiez le voir en action. Pour mon temps, j'ai simplement exécuté le programme plusieurs fois et pris les valeurs les plus rapides et les plus lentes comme plages.
la source
Python
Devrait avoir une période d'environ 2 ^ 512.
la source
perl, 44 octets
Je sais que ce n'est pas du golf de code, mais j'ai toujours été fan de prendre les bits de poids faible d'une simple fonction quadratique, par exemple:
La période dépasse 3 milliards, mais je n'ai plus d'espace disque pour en calculer davantage.
la source
$x=1/7;print substr($x*=4-4*$x,9,1)%2while 1