samedi 21 décembre 2013

générateur de nombre pseudo aléatoire

Je suis en train de lire A new kind of science de Stephen Wolfram. Au chapitre 4 il mentionne qu'il a fait l'expérience suivante.
soit un nombre entier N

  1. Si N est impaire on l'incrémente
  2. On multiplie N par 3 et on divise par 2
  3. On recommence à l'étape 1
C'est ce qu'on appelle une fonction itérative, la valeur de f(N)=f(N-1)*3/2

Wolfram mentionne que le bit le plus faible de cette fonction itérative est aléatoire. C'est à dire qu'il est impossible de prédire si le nombre à la position x de la suite de nombres générés par itération sera pair ou impaire.

Écrire une fonction pour multiplier un nombre par 3 pour ensuite le diviser par 2 est simple à réaliser même en assembleur sur un petit MCU comme le PIC10F200. Puisque les générateurs de nombres pseudo aléatoire sont très utiles en informatique j'ai voulu vérifier si je pouvais réellement obtenir une suite de bits aléatoires avec cette fonction. J'ai donc pris un PIC10F200 et un petit haut-parleur que j'ai branché sur GP2.

J'ai écris 4 versions de la fonction f(N)= f(N-1)*3/2 pour les de différentes grandeurs d'entiers, 8 bits, 16 bits, 24 bits et 32 bits.

façon simple de tester un PRNG

Pour vérifier si un PNRG est vraiment aléatoire il existe une méthode simple quoique pas très scientifique. On écoute la série de bits produits et si le son est du bruit blanc, (le bruit produit par une chute d'eau), alors le générateur est bon. Il ne faut pas distinguer de cycles dans le bruit produit. Seulement un shhhhhh uniforme.

Donc la boucle principale du programme appelle la fonction itérative et vérifie si le résultat est pair ou impaire. Si c'est pair la sortie GP2 est mise à 1 sinon elle est mise à zéro. Le TIMER0 est utiliser pour créer un délais entre chaque appel de la fonction itérative pour que le spectre sonore soit dans l'audible.

Résultat

  • fn_iter8b. Mauvais on a l'impression d'entendre une seule tonalité
  • fn_iter16b. Mieux mais encore mauvais. On entend une tonalité mais il y a du chirp.
  • fn_iter24b. Beaucoup mieux. Beaucoup de bruit blanc mais lorsqu'on est attentif on détecte des cycles. Bon pour une application pas trop exigeante.
  • fn_iter32b. Très bien. Qualité suffisante pour des jeux vidéo ou autres application non critique.

J'ai aussi tester la fonction lfsr_rand que j'ai utilisé pour la chandelle électronique. Le résultat est presque aussi bon que pour fn_iter32b. L'avantage du lfsr_prng est qu'il nécessite moins d'instructions. Disons que sur un MCU 16 ou 32 bits fn_iter32b serait un bon choix car le nombre d'instructions nécessaires serait réduit de 50% ou moins.

code source

Aucun commentaire:

Publier un commentaire