Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°44 - mars 2015 > La génération aléatoire de nombres dans la (...)

La génération aléatoire de nombres dans la TI82-83.
Moteur de recherche

Situation de classe
En introduction à l’échantillonnage en classe de seconde j’utilise le TP 2 du chapitre 4 Statistiques du manuel scolaire Repères (Hachette 2012) ci-dessous :

PDF - 437 ko
TP2 Repères Seconde édition 2012

Le calcul par la machine des 10 000 lancers simulés et l’affichage du rang du tirage et de la fréquence d’apparition du 1 dans ce tirage met 3 minutes et 20 secondes (Avec ma TI-83 Plus SILVER EDITION, cela n’est pas le cas avec tous les modèles, j’ai pu m’en rendre compte en classe).
Pour un programme plus rapide (Exécution en 2 minutes et 30 secondes avec ma TI-83 Plus SILVER EDITION, avec la TI82 Stats.fr de mon fils cela met 6 minutes 8 secondes) on peut utiliser ça :

PROGRAM:SIMUL2
:EffList L1,L2
:For(I,1,100)
:I->L1(I)
:somme(EntAléat(0,1,100))/100->L2(I)
:Disp I,L2(I)
:End

La commande somme(EntAléat(0,1,100))/100->L2(I) stocke dans L2(I) la fréquence d’apparition du 1 parmi 100 nombres aléatoires entiers compris entre 0 et 1, c’est bien ce que l’on veut obtenir
Après l’affichage du graphique, on peut inviter les élèves à ajuster la fenêtre en rentrant Ymin=0 et Ymax=1 afin de constater qu’il n’y avait pas de points situés en dehors de la fenêtre obtenue avec ZoomStat, puis revenir à ZoomStat.
Je fais ce TP depuis plusieurs années et je n’avais jamais eu de problème auparavant, je passais dans les rangs vérifier que tous les écrans affichaient bien le nuage de points attendu, ma calculatrice à la main pour leur montrer ce que j’obtenais moi-même, un nuage de points semblable au leur mais pas identique. Ce que je n’avais pas appréhendé c’est qu’ils avaient tous le même nuage de points !!! Je l’ai constaté cette année car j’ai changé ma façon de procéder, mes élèves étant plus aguerris dans la programmation de la calculatrice que les années précédentes, j’ai programmé en même temps qu’eux l’algorithme sur l’émulateur en ligne de la TI, ce que je faisais aussi avant mais comme la programmation me prenait plus de temps et que cet émulateur n’est pas stable (il se bloque souvent si on ne l’utilise pas en continu), je n’arrivais jamais jusqu’à afficher le graphique, cette fois-ci j’ai pu l’afficher.
Une élève m’a alors fait remarquer que mon nuage de points était exactement le même que le sien ! Et 32 élèves sur 34 de constater la même chose ! Les deux seuls qui avaient un graphique différent avaient des machines d’occasion, les autres des machines neuves, sorties d’usine, n’ayant jamais utilisé la fonction nombre aléatoire.
Il était donc évident que toutes les machines généraient la même suite de nombres aléatoires. Cela pose quand même problème, et les élèves étaient un peu interloqués, je leur ai alors dit que j’allais me renseigner sur ce phénomène et reviendrait vers eux quand j’aurais une réponse. J’avais souvenir d’avoir lu ou entendu quelque part que la génération de nombres aléatoires était quelque chose de délicat, donc je me suis mis à la recherche d’une solution pour continuer à utiliser ce TP avec des nuages de points différents pour chaque élève et à y être à trouver comment sont générés les nombres aléatoires dans leur machine.
Recherche d’une solution pour continuer à utiliser ce TP
Dans un premier temps je suis à la recherche d’une solution pour mon TP, j’utilise alors deux listes de collègues que je sais être capables de me renseigner :
- La liste du comité de rédaction de Mathem@tice ;
- La liste du groupe GENT (académie de Montpellier, cercle d’étude pour la production de ressources mathématiques dans l’ENT de l’Académie de Montpellier).
La première information et bonne piste vient d’Alain Busser (Mathém@tice) :
"Un bon moyen de tester (sans acheter d’autres calculatrices) c’est d’utiliser un émulateur. Avec ça on voit que le nombre vidéo-projeté est le même que celui de plusieurs calculatrices dans la salle, l’effet est garanti !"

C’est exact, si la machine est neuve, à la première utilisation de la fonction NbAléat elle affiche 0.9435974025, c’est la même chose avec l’émulateur en ligne de la TI (menu MATH, PRB, fonction rand ou NbAléat).
Ceci est expliqué dans le manuel de la TI83.

PDF - 51.6 ko
MATH PRB TI83

"La méthode utilisée est un générateur congruentiel de Lehmer (que je décris page 25 du doc "CoffeeScript" des Regards croisés sur l’algorithmique et la programmation numéro 3 des fois que...). L’algorithme est de Pierre L’Ecuyer et décrit ici.
Reste à trouver les nombres utilisés, dans la Ti89 je crois me rappeler qu’ils s’appellent seed1 et seed2 (ou approchant, le nom exact se trouve en appuyant sur "catalog" puis sur "s")
".

Merci Alain, je lis, me documente, je progresse (Les valeurs de seed1 et seed2 sont dans le document de L’Ecuyer mais je ne les ai pas "vues", page 7).

"On peut retrouver certaines choses en multipliant les nombres aléatoire d’une Ti par un des entiers donnés dans l’article ou en utilisant le débogueur de l’émulateur Ti pour chercher des entiers particuliers dans la ROM de la calculatrice."

Bon, là j’ai cherché, testé, mais rien trouvé ...

"Par contre il semble que la calculatrice aime réinitialiser le générateur (possible aussi que sur certaines Ti on n’utilise qu’un seul générateur au lieu de 2 ; dans ce cas on peut apprendre des choses en divisant un nombre aléatoire par le précédent plusieurs fois et en regardant si un entier n’apparaît pas de temps en temps)".

Voilà quelque chose qui a fait avancer mes recherches, facilitées par le message de Fabien Cayla (GENT) :
"Sur la TI, la méthode pour générer des nombres pseudo aléatoires est la méthode de Lhemer, en gros c’est une suite arithmético-géométrique modulo un nombre.
Donc deux calculatrices qui sortent de l’usine donneront exactement la même suite de nombres pseudo aléatoires :
le premier terme de la suite , puis le second ...
Sur la TI, on peut remettre le générateur de nombres pseudo aléatoires à 0
on entre :

0->NbAléat
et quand on entre :
NbAléat
le nombre qui est donné est 0.9435974025
Cela surprend toujours beaucoup les élèves d’avoir tous le même nombre "au hasard" ! (et il peut s’en suivre une discussion intéressante...)
"

Si vous faites cela sur votre machine (n’ayez pas peur, il n’y a pas de risque ...) elle affiche ensuite 0.908318861 puis 0.1466878292 ...
J’ai donc trouvé comment rendre mon TP à nouveau fonctionnel, il suffit de dire aux élèves de choisir un nombre entier entre 1000 et 10000 autre que leur année de naissance ou l’année en cours (lol), de le stocker dans NbAléat, ils obtiennent ainsi des suites de nombres aléatoires différentes.
Il est à noter que ce nombre ne correspond pas au rang du nombre aléatoire dans la suite, en effet si on entre 1->NbAléat on n’obtient pas 0.908318861 mais 0.7455607728 (Je n’ai pas encore trouvé comment faire démarrer le générateur au rang 1 directement mais est-ce bien utile ? ...). [1]

Générateurs de nombres aléatoires
Mon TP est de nouveau opérationnel mais je poursuis mes recherches, et si je pouvais trouver quelque chose d’intéressant à faire en Spécialité mathématique avec ces suites ?
Je continue donc de chercher comment sont générés ces nombres aléatoires dans la TI, je tombe alors sur Random Number Generation, un document qui explique comment sont générés les nombres aléatoires dans un processeur de signaux TMS, alors que le processeur de la Ti83 est un Z80 de Zilog, ça n’a rien à voir mais je me dis que ça doit être à peu près pareil surtout après être tombé sur TMS320C55x DSP Library Programmer’s Reference ...
Ne sachant pas exactement vers où chercher j’essaie toutes les suites de Lehmer que je peux trouver en ligne et que je teste avec le fichier ci-dessous :

OpenDocument Spreadsheet - 15.3 ko
Générateur de nombres aléatoires : suite de Lehmer

Il est à noter que la calculatrice en mode Suite ne permet pas ces calculs dès que les nombres sont "un peu grands", avec a=31415821, b=1 et m=10^8 par exemple (tiré de l’exercice de la page 2 de l’article de T.Lambre) les premiers termes sont 31415822, 40519863 et 62952524 normalement, à la calculatrice on obtient 31415822, 40519860 et 68705100 :(
Je ne trouve pas, je me dis alors que si je trouvais la période de la suite de nombres pseudo-aléatoires de ma calculatrice, je pourrais peut-être trouver cette suite grâce à ce paramètre, je programme donc un algorithme afin de déterminer cette période :

PROGRAM:PERIODE
:0->rand
:rand->X
:0->C
:While rand≠X
:C+1->C
:End
:Disp C

Une dizaine d’heures plus tard et une alerte de la calculatrice qui me dit que les piles doivent bientôt être changées me font stopper le programme, je demande à ma machine qui me dit que C=1326830, ainsi donc la machine génère plus de 1326830 nombres aléatoires, je trouve cela énorme !
Mes recherches ont été relancées par un message de Fabien Cayla :
Avec ton mail j’ai enfin retrouvé un article du Bulletin vert, n°491, de l’APMEP qui en parlait. Il s’agit d’un article de Thierry Lambre, Qu’est-ce qu’un générateur de nombres au hasard ?.
Thierry Lambre parle du générateur de la TI voyage ( p 674,675), mais sur les deux premiers termes c’est les même que sur ma TI82 stat.fr, donc c’est peut-être le même générateur.
Si c’est le cas je me suis un peu avancé dans ma première explication car il semble que la suite de nombres pseudo aléatoires de la TI soit un couplage de deux suites de Lhemer et non d’une.
Thierry Lambre parle d’une période de de 2*10^18 ....qui me semble donc difficilement visible même en programmant.

EUREKA, merci Fabien, c’est bien la même ! Je ne risquais pas de trouver la période avec mon programme ! Il faut le laisser tourner pendant 2*10^18/49 ≈ 4,08*10^16 s c’est-à-dire 1,29 milliards d’années ... (J’ai obtenu le nombre de 49 nombres aléatoires générés à la seconde par la TI83 grâce au programme PERIODE, ce nombre diffère selon les modèles).
Le programme qui génère les dix premiers nombres aléatoires en Python :

  1. def lehmer1(n):
  2. if n==0:
  3. return 12345
  4. else :
  5. return (lehmer1(n-1)*40014)%(2**31-85)
  6. def lehmer2(n):
  7. if n==0:
  8. return 67890
  9. else:
  10. return (lehmer2(n-1)*40692)%(2**31-249)
  11. def alea(n):
  12. alea= (lehmer1(n)-lehmer2(n))%(2**31-86)
  13. return alea/(2**31-86)
  14. for i in range(1,10):
  15. print(round(alea(i),10))

Télécharger

Une feuille de classeur OpenOffice pour les 30 premiers nombres aléatoires :

OpenDocument Spreadsheet - 19.2 ko
Générateur de nombres aléatoires : TI

J’ai maintenant la matière pour proposer quelque chose à mes élèves de Spécialité mathématique, et ce que je vais leur demander c’est de programmer l’affichage des 10 premiers nombres aléatoires générés par une calculatrice TI sortie d’usine.
Pour cela, il me faut leur montrer :
- ce qu’est la commande NbAléat et les nombres qu’elle génère à la sortie d’usine.
- ce qu’est une suite de Lehmer.
- ce qu’est le générateur de nombres aléatoires de la TI.
- comment calculer le reste dans la division euclidienne puisque cette commande n’existe pas dans la TI.

PDF - 104.4 ko
Le générateur de nombres aléatoires de la TI82-83
OpenDocument Text - 103.9 ko
Le générateur de nombres aléatoires de la TI82-83

La programmation de l’algorithme dans la calculatrice :

:2^31->M
:M-85->P
:M-249->Q
:12345->S
:67890->T
:40014->A
:40692->B
:For(I,1,10)
:A*S-int(A*S/P)*P->S
:B*T-int(B*T/Q)*Q->T
:S-T-int((S-T)/(P-1))*(P-1)->W
:W/(P-1)->R
:Disp R
:Pause
:End

Avec Algobox

AlgoBox - 2.3 ko
rand

Il y a un problème avec le logiciel car il y a un bug dans la commande % qui renvoie le reste dans la division euclidienne de a par b quand on tape a%b, en effet (493972830-615096481)%2026359911 renvoie -121123651 au lieu de 1950599823
donc la suite des nombres aléatoires générés n’est pas bonne ! On peut contourner ce problème en changeant la ligne

W PREND_LA_VALEUR (S-T)%(p-1)
en W PREND_LA_VALEUR (S-T+p-1)%(p-1).

de plus il ne donne pas avec assez de chiffres après la virgule !
***Algorithme lancé***
0.9435974
0.90831886
0.14668783
0.51470195
0.40580964
0.73381231
0.043991988
0.33936253
0.99546634
0.20034026
***Algorithme terminé***
On peut corriger cela en programmant mais le but n’est pas là à mon sens, donc je préfère utiliser Algobox en ligne, basé sur Javascript.

VARIABLES
        p EST_DU_TYPE NOMBRE
        q EST_DU_TYPE NOMBRE
        a EST_DU_TYPE NOMBRE
        b EST_DU_TYPE NOMBRE
        I EST_DU_TYPE NOMBRE
        W EST_DU_TYPE NOMBRE
        alea EST_DU_TYPE NOMBRE
        S EST_DU_TYPE NOMBRE
        T EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
        p PREND_LA_VALEUR pow(2,31)-85
        q PREND_LA_VALEUR pow(2,31)-249
        a PREND_LA_VALEUR 40014
        b PREND_LA_VALEUR 40692
        S PREND_LA_VALEUR 12345
        T PREND_LA_VALEUR 67890
        POUR I ALLANT_DE 1 A 10
                DEBUT_POUR
                S PREND_LA_VALEUR (a*S)%p
                T PREND_LA_VALEUR (b*T)%q
                W PREND_LA_VALEUR (S-T+p-1)%(p-1)
                alea PREND_LA_VALEUR W/(p-1)
                AFFICHER*  round(alea*10000000000)/10000000000
                FIN_POUR
FIN_ALGORITHME

Début de l’algorithme
0.9435974025
0.908318861
0.1466878292
0.5147019505
0.4058096418
0.7338123112
0.0439919875
0.339362525
0.9954663411
0.2003402618
Fin de l’algorithme
Cette activité a beaucoup plu aux élèves de Spé Maths, certains sont allés jusqu’à chercher et trouver comment obtenir la bonne suite de nombres dans le logiciel Algobox.
J’ai repris le TP avec mes secondes, ils avaient déjà programmé le lancer des 10000 pièces, il m’a suffit de leur demander de choisir un nombre entre 1000 et 10000 et de le stocker dans NbAléat avant de lancer le programme SIMUL2 (J’en ai profité pour leur montrer comment optimiser le programme pour gagner du temps).
Enfin j’ai testé le TP dans son intégralité dans la classe de seconde que je n’ai qu’en AP :
- Ils ont utilisé l’énoncé du Hachette Repères tel quel et constaté qu’ils obtenaient tous le même nuage, je leur ai alors expliqué pourquoi, ils ont fait fonctionner la fonction NbAléat après réinitialisation pour constater de visu que la suite de nombres était la même sur le simulateur que sur leur machine.
- Je leur ai demandé de choisir un nombre entre 1000 et 10000 et de le stocker dans NbAléat avant de lancer le programme SIMUL2

Bibliographie
- Générateur de nombres pseudo-aléatoires, article Wikipédia
- Derrick Lehmer sur Wikipédia
- Pierre Lécuyer, site personnel
- P. L’Ecuyer, Efficient and Portable Combined Random Number Generators, Communications of the ACM, 31 (1988), 742—749 and 774.
- Bulletin vert, n°491, de l’APMEP, Thierry Lambre, Qu’est-ce qu’un générateur de nombres au hasard ?.


notes

[1Cette question a été résolue suite à un échange de mail avec François Pirsch, l’auteur du site Proglab, un site qui propose Algobox en ligne et une conversion Algobox <-> Javascript. Alors que j’utilisais ce site je suis tombé sur un bug que j’ai signalé à F.Pirsch, suite à quoi je lui ai fait part de cet article qui utilisait son logiciel, il m’a alors dit avoir implanté ce générateur en Javascript deux ans plus tôt : ici. Les nombres générés sont bien ceux de la TI mais ils ont un nombre de décimales supérieur à ceux de la TI. J’ai repris ce programme en Algobox en faisant en sorte d’obtenir exactement les mêmes nombres que sur la TI : ici. Avec les mêmes variables que le programme proposé dans cet article : ici.
A noter un bug de la calculatrice, si vous entrez la graine 1 dans le programme, l’algorithme donne :
0.7455607728
0.8559005971
0.2253600617
0.469229188
0.6866902137
0.0849241336
0.0800630669
0.6219079175
0.1272157551
0.2646513087
alors que la calculatrice donne :
0.7455607728
0.8559005971
0.2253600617
0.469229188
0.6866902136
0.0849241336
0.0800630669
0.6219079175
0.1272157551
0.2646513087
Avec les grands nombres, la calculatrice est quelquefois défaillante ...
Le fichier tableur qui propose ce générateur :

OpenDocument Spreadsheet - 19.4 ko
Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197