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

; NOM: Sound Of Math ; DESCRIPTION: soit la fonction itérative f(n)= f(n-1)*3/2 ; on utilise le bit le plus faible de la valeur obtenu à chaque itération ; pour basculer l'état de la sortie GP2. Quel son va résulter de cette ; opération arithmétique? ; Si ce bit est aléatoire ça devrait produire un son blanc (white noise). ; AUTEUR: Jacques Deschênes ; DATE: 2013-12-21 include p10f200.inc radix dec __config _WDTE_OFF AUDIO EQU GP2 TMR0_CNT EQU 40 LFSR_MASK EQU 0x7FFFF159 audio_low macro bcf GPIO, AUDIO endm audio_hi macro bsf GPIO, AUDIO endm ; variables appvar udata 16 nval res 4 rand res 4 temp res 4 org 0 movwf OSCCAL goto init fn_iter8b ; fonction itérative f(n)=f(n-1)*3/2 nval 8 bits movlw 1 ; si nval est impaire btfsc nval,0 ; incrémente nval addwf nval, F clrc rlf nval, W ; W=2*nval addwf nval, F ; nval = nval+W rrf nval, F ; nval = nval/2 retlw 0 fn_iter16b ; même fonction mais avec nval 16 bits movlw 1 ; si nval est impaire btfsc nval,0 ; incrémente nval addwf nval, F skpnc addwf nval+1,F clrc ; temp = 2*nval rlf nval, W movwf temp rlf nval+1,W movwf temp+1 movfw temp ; nval = nval + temp addwf nval,F skpnc incf temp+1,F movfw temp+1 addwf nval+1,F rrf nval+1,F rrf nval,F retlw 0 fn_iter24b ; même fonction mais avec nval 24 bits movlw 1 ; si nval est impaire btfsc nval, 0 ; incrémente nval addwf nval, F skpnc addwf nval+1,F skpnc addwf nval+2,F clrc ; temp=n*2 rlf nval,W movwf temp rlf nval+1,W movwf temp+1 rlf nval+2,W movwf temp+2 movfw temp ; nval +=temp addwf nval,F skpnc incf temp+1,F movfw temp+1 addwf nval+1,F skpnc incf temp+2,F movfw temp+2 addwf nval+2, F clrc rrf nval+2,F rrf nval+1,F rrf nval, F retlw 0 fn_iter32b ; même fonction mais avec nval 32 bits movlw 1 ; si n est impaire btfsc nval, 0 ; incrémente n addwf nval, F skpnc addwf nval+1,F skpnc addwf nval+2,F skpnc addwf nval+3,F clrc ; temp=n*2 rlf nval,W movwf temp rlf nval+1,W movwf temp+1 rlf nval+2,W movwf temp+2 rlf nval+3,W movwf temp+3 movfw temp ; nval += temp addwf nval,F skpnc incf temp+1,F movfw temp+1 addwf nval+1,F skpnc incf temp+2,F movfw temp+2 addwf nval+2, F skpnc incf temp+3, F movfw temp+3 addwf nval+3, F clrc rrf nval+3,F rrf nval+2,F rrf nval+1,F rrf nval, F retlw 0 ; LFSR de 32 bits ; référence: http://www.ece.cmu.edu/~koopman/lfsr/index.html ; ce lfsr ne doit pas être initialisé avec la valeur 0xFFFFFFFF ; SORTIE: retourne la valeur dans rand_val lfsr_rand rrf rand+3,W ; rotation du LFSR 1 bit vers la droite rrf rand, F rrf rand+1,F rrf rand+2,F rrf rand+3,F btfsc rand+3,7 goto lfsr_rand_exit movlw LFSR_MASK & 0xFF xorwf rand movlw (LFSR_MASK>>8) & 0xFF xorwf rand+1 movlw (LFSR_MASK>>16) & 0xFF xorwf rand+2 movlw (LFSR_MASK>>24) & 0xFF xorwf rand+3 lfsr_rand_exit movlw 0x1F andwf rand,W ; modulo 32 movwf nval retlw 0 init movlw H'81' option movlw b'1011' tris GPIO movlw 2 movwf nval clrf TMR0 main movlw ~TMR0_CNT addwf TMR0, F call fn_iter32b ; fonction itérative générant le bit pseudo aléatoire. ; call lfsr_rand btfsc nval,0 goto pin_high pin_low audio_low goto delay pin_high audio_hi nop delay ; délais d'échantionnage movfw TMR0 skpz goto $-2 goto main end