Suite au bug OpenSSL de Debian, je me suis à nouveau intéressé de près aux générateurs de nombres pseudo-aléatoires (PRNG). J'ai commencé à écrire la bibliothèque Hasard qui contient plusieurs algorithmes pour générer des nombres et des fonctions de haut niveau : int(min, max), bool(), bytes(size), etc.

Outils ENT et Dieharder

J'ai utilisé le programme ENT pour tester la qualité des algorithmes. ENT utilise :

ENT n'accepte en entrée que des fichiers contenant des octets (pseudo-)aléatoires. On ne peut donc pas tester la qualité d'un générateur de nombre flottants par exemple. Exemple de sortie (algorithme RANDU avec l'opérateur pow2(8)) :

Entropy = 6.000000 bits per byte.

Optimum compression would reduce the size
of this 262144 byte file by 25 percent.

Chi square distribution for 262144 samples is 786432.00, and randomly
would exceed this value 0.01 percent of the times.

Arithmetic mean value of data bytes is 126.0000 (127.5 = random).
Monte Carlo value for Pi is 2.999862669 (error 4.51 percent).
Serial correlation coefficient is 0.322338 (totally uncorrelated = 0.0).

Il existe également le programme Dieharder qui accepte en entrée des nombres de 32 bits non signés dans un fichier binaire ou un fichier texte. Il utilise des tests bien plus rigoureux, mais comme je ne sais pas les interpréter, je ne vais pas commenter.

Représentation visuelle

C'est pas très rigolo tout ça, alors voyons un peu des dessins et schémas qui permettent de distinguer le bon chasseur du mauvais chasseur. Image générée à partir des 8 bits de poids faible de l'algorithme RANDU :

Chaque pixel utilise une valeur du générateur comme couleur. On voit clairement que l'algorithme n'est pas du tout aléatoire ! Pour reproduire l'image :

$ cd tests
$ ./gen_files.py --rng=randu --op=pow2 --bits=8 randu.dat
$ ./draw_pil.py --width=300 --height=300 randu.dat

Une autre façon de représenter des nombres est d'utiliser un axe 2D avec x=random() et y=random() :

On voit qu'il existe très peu de combinaisons (x, y) : j'en dénombre 16. Pour reproduire cette image :

$ ./gnuplot.py randu.dat --point=2

La page web graphics présente d'autres images.

Script de tests de la bibliothèque Hasard

Le script gen_files.py génère un fichier au format texte plat qui contient les nombres générés par l'algorithme RANDU pour l'opérateur pow2(8) (génère un nombre dans l'intervalle [0; 255]). Lire file_format.rst pour voir le format de ce fichier. Le script file_info.py calcule l'entropie des nombres générés, la valeur maximale et la valeur minimale.

$ ./file_info.py randu.dat
Engine: randu
Seed: linux_urandom
Range: 0..255
Operation: pow2
Count: 262144
Minimum: 1
Maximum: 251
Entropy: quality=75.00%, value=6.0000/8.0000

On voit que seul 6 bits sur 8 sont réellement aléatoires (2 bits sont invariants) et que l'intervalle annoncé est incorrect : 0..255 versus 1..251.

J'aime bien l'algorithme RANDU car il est vraiment mauvais et il permet donc de tester l'outillage de test :-)

Pour la suite

Ma bibliothèque est encore en chantier. J'ai beaucoup travaillé sur l'outillage pour tester la sortie des algorithmes en comparant avec d'autres bibliothèques comme Python, PHP ou la libc. La version 0.2 n'inclut par encore ce travail, ça sera le cas pour la prochaine version 0.3 qui n'est pas encore publiée. En attendant, vous pouvez utiliser le dépôt Mercurial.

Je ne sais pas trop ce qu'Hasard va donner au final, mais en tout cas ça avance :-)