Re: fonction rand : comment fonctionne-t-elle vraiment?

par **sandro** Mer 18 Avr - 20:06

perso, je vois 3 hypothèse :
1) il s'agit uiquement de rotations, permutations et d'échanges de chiffres avec un emplacement spécial de la ram
2) il s'agit d'un calcul (éventuellement accompagné de rotations et/ou de permutations) quivie d'un modulo 1
3) un mélange des 2

Pour voir si ça aide, un extrait de l'exécution de la fonction (en asm). regardez seulement la dernière instruction de chaque adresse, les autres sont les instructions précédentes:

Spoiler:

Sandro

par mdr1 Jeu 19 Avr - 16:44

[quote=linkakro]Inconvénient probable d'une récurrence classique mathématique :
si la suite est convergente, alors on aurait pas de bon aléatoire après un certain nombre d'itérations.
La suite ne peut pas être divergente car elle est bornée par 0 et 1.
Elle devrait donc n'être ni convergente ni divergente, et peut-être contenir des tests.[/quote]
Attention, tu fais une confusion : dire qu'une suite est divergente ne signifie pas qu'elle tend vers plus ou moins l'infini, mais veut simplement dire qu'elle n'est pas convergente.
Pour les tests, développe ton idée.

[quote=sandro]perso, je vois 3 hypothèse :
1) il s'agit uiquement de rotations, permutations et d'échanges de chiffres avec un emplacement spécial de la ram
2) il s'agit d'un calcul (éventuellement accompagné de rotations et/ou de permutations) quivie d'un modulo 1
3) un mélange des 2[/quote]
Bof pour la 1), parce-que quand on fait 0→rand, on a tous les mêmes valeurs, après. À moins que l'OS ne remette à 0 la partie de la RAM quand c'est nous qui initialisons.

Sinon, regardez ce test intéressant :

* mettez par exemple 78 dans rand : 78→rand
* calculez rand : rand = 0.1537402492
* calculez rand : rand = 0.7602419981
* mettez 0.1537402492 dans rand
* calculez rand : rand = 0.9435974025

Donc après une même valeur précédent de rand, il n'aura pas forcément la même valeur la fois suivante.

Donc il ne s'agit pas d'une suite basée uniquement sur le terme précédent, et c'est peut-être même pas une suite.

par **linkakro** Jeu 19 Avr - 18:23

Je suis allé jusqu'à saisir les 14 chiffres significatifs de nombres aléatoires, et j'observe la même chose que toi avec 10 chiffres

Ce que je veux dire par "contenir des tests" est d'utiliser des conditions à l'intérieur de l'algorithme de génération.
En effet des conditions peuvent transcender des algorithmes et rendre impossible une modélisation mathématique.
Du genre ln(sin(x+2(sin(x)<.5))-3(cos(x)>.5)). Ceci est reconnu par une calculatrice mais comment définir une formule équivalente mathémathiquement ?
Dès qu'un test se promène dans un algorithme cela devient plus difficile d'analyser son fonctionnement.
Mais bon, passons, ce n'est pas un axe primordial de recherche.

Cela pourrait bien être une suite, mais nous savons déjà qu'initialiser rand avec X->rand ne produit pas le même effet que lire rand.
Qu'on ai toujours une même série après une même initialisation est tout-de-même troublant s'il n'y a pas de comportement récurrent. (ou récursif)

Merci pour la mise au point de la divergence. Je confondait aussi avec la notion de limite.
convergent : limite finie
divergent : pas de limite finie ou même pas de limite du tout.
(-2)^2 par exemple est divergente sans limite.

par mdr1 Ven 20 Avr - 18:58

Pour les tests, facile de définir mathématiquement : il suffit de définir la fonction par morceaux.

PS : pour le prog asm de sandro, c'est impossible à décrypter puisque faut se saouler à ne regarder que chaque dernière instruction. C'est mortel !

par **sandro** Ven 20 Avr - 19:07

oui, c'était juste pour voir si ça donnait une idée (vu que c'était déjà fait, ça ne coutait rien de le poster). Par contre, ce qu'il me faudrait serrait un désassembleur, ce serait bien plus pratique.

Sandro

EDIT : on optient la même suite sur TI89titanium. Quelcu possède-t-il un autre model non-z80 non testé (ou autre model de TI non testé (peut-être collège?)

par mdr1 Mer 25 Avr - 7:41

Un désassembleur ? Calcsys, tout simplement.
Mais attention, quand tu désassembles un prog enregistré en RAM ou en archive, les sauts absolus ne tomberont pas au bon endroit (car le prog n'est pas enregistré à $9D95), mais les bons relatifs seront OK.

par **sandro** Mer 25 Avr - 14:17

oui, sauf que mo problème est de décompiller des bouts de rom, et surtout d'avoir la possibilité de manipuler ensuite comme du teste. Juste pour voire un endroit spécifique, le débuggueur asm de Wabbitému est totalement apte, mais il ne permet pas vraiment de récupérer des centaines de lignes de code sous format texte.

Merci quand même
Sandro

par **sandro** Sam 5 Mai - 9:57

J'ai réussit à récupérer des roms décompilées ici. J'ai donc commencé à repérer le code à l'aide du débuggueur asm de Wabbitému et de ces fichiers (même si il y a quelques différences malgrès un même OS), mais je suis loin d'avoir finit (je suis obligé de faire un clic pour avancer d'une instruction (sinon ça va trop vite et je vois rien si je met juste executer)).

Par ailleurs, j'ai fais quelques mesures : il faut environt 0.033 secondes pour que la TI83+ execute :rand dans un programme. Celà signifie, la fréquence du processeur de la TI83+ étant bridé à 6MHz, qu'il y a environt 200 000 T-States, donc environt 20 000 instructions asm executées (même si beaucoup le sont plusieures fois) (je compte une moyenne de 10 T-States par instructions même si c'est peut-être un peu plus ou un peu moins).

Sinon, j'ai déjà décripté un petit bout de code :

Code:: xor a rrd inc hl rrd inc hl rrd inc hl rrd inc hl rrd inc hl rrd inc hl rrd inc hl rrd inc hl ret

Cette routine prend sauf erreur de ma part en "entrée" le registre hl qui pointe vers un nombre de 8 octets. Il remplace ce nombre par le quotient de la division du nombre par 16 et renvoie le reste dans a. à la fin, hl vaut sa valeur de départ +8, c'est à dire qu'il pointe l'octet juste après le nombre modifié.

Sandro

0123 4567

par **persalteas** Dim 6 Mai - 7:01

Alors là j'en reviens pas...

Ces ROMs décompilées valent leur pesant d'or...

Content que tu aies enfin trouvé...

par **sandro** Dim 6 Mai - 18:45

Oui, c'est sur quelles ont de l'intéret. Sinon, le lien du site d'où elles viennent : [Vous devez être inscrit et connecté pour voir ce lien] : le site de Brandon (grand merci à lui, même si je ne crois pas qu'il passe ici).

Par contre, c'est vraiment gallère retrouver le code de la fonction, vu qu'il est dispersé à travers la ram et que certaines boucles snt executées des dizaines de fois.

Sandro

par **persalteas** Dim 6 Mai - 19:34

Bonne chance Content

je connais le site de Brandon, j'ai visité tous les sites des membres de detachedsolutions.

par Invité Sam 19 Mai - 14:16

Bonjour, j'ai peut être du nouveau... désolé pour le mini déterrage. Alors info ou intox?
Hier le prof de maths dans le cadre d'un cours sur les suites nous a distribué des exemples, dont certains sous forme de programmes. Il a dit que c'est en servant du programme suivant que la TI génère de l'aléatoire: en prenant N comme la N-ième fois qu'on se sert de la fonction aléatoire, il me semble. Il n'en a pas dit plus. Le code:

Code:: 0.5->X For(I,1,N partDèc(9821X+0.211327)->X End Disp x

Cependant je n'ai pas trouver de résultats convaincants pour confirmer cela... j'essayerai de me renseigner.

par **sandro** Sam 19 Mai - 17:13

Merci pour la tentative, mais ça ne PEUT pas être ça (sans compter que ça ne corespond pas aux résultats de la TI) car X0 contient une décimal, mais tous les suivants (toute les valeurss suposées comme nombres aléatoires, ont au maximum 6 décimales, car multiplier par un entier n'augmente jamais le nombre de décimales, et ajouter un nombre à 6 décimales ne peut pas faire augmenter le nombre de décimales au-delà de 6. Donc tous les nombres aléatoires n'auraient que 6 décimales, or ils en ont 14, donc c'est algorithme n'est pas le bon sur les TI z80.

Par contre, possible que cet algorithme soit valide sur les TI-Collège par example.

Merci quand même
Sandro

par Invité Sam 19 Mai - 20:05

De rien, je demanderai plus de précision dès que possible.

par **sandro** Sam 19 Mai - 21:36

merci, moi mes 3 profs de maths d'impatience veulent tous le savoir depuis que je leur ai parlé de ma recherche (dont un qui m'a demander de le contacter par mail même si je trouve après la fin de l'année)

par Invité Dim 20 Mai - 7:50

La question fait donc des émules. Je suis conscient que cela enleverai l'euphorie de la recherche, mais Texas Instrument ne pourrait pas directement nous renseigner? Mais vu que cela n'est pas libre (il me semble bien) j'en doute...

par **sandro** Dim 20 Mai - 17:53

j'en doute aussi fortement, vu la gueule qu'ils ont apparament fait quand les clé de criptage des roms ont été craquées (il semblerait qu'ils ait été jusqu'à faire de procès (perdus)), je ne crois pas qu'il accèpteront de nous dévoiler un bout de rom décripté. A la limite l'algorithme, mais même là j'en doute.

Sandro

PS : je vais quand même leur envoyer un mail à l'occasion pour voir.

par Invité Dim 20 Mai - 20:41

Ok, et comme on dit, qui ne tente rien n'a rien. Ils finiront peut être par craquer si tout le monde le leur demande ( :D )

par **sandro** Lun 21 Mai - 16:09

Bon, j'ai demandé à Jarrety s'ils connaissaient ou s'ils savaient où écrire, il m'ont répondu qu'ils ne connaissaient pas l'algo, mais aucune réponse pour où écrire.
EDIT : j'ai envoyé la même requête à [Vous devez être inscrit et connecté pour voir ce lien]

par **persalteas** Lun 21 Mai - 16:25

Ouais, Jarrety c'est les vendeurs, pas les ingénieurs...

par **sandro** Lun 21 Mai - 17:03

Je sais, mais je pensais qu'ils saurraient où je dois m'addresser (et j'avais plus l'addresse de TI-Cares sous la main).

Bon, à voir si à TI-Cares ils sauront me répondre/rediriger

par maxence Mar 5 Juin - 19:47

Lors d'un cours sur les radians, notre prof de maths nous a dis que l'algorythme utilisé pour la fonction rand se servait de pi, car ses décimales se comportent comme des nombres aléatoir ! (en effet environ 1/10 de fréquence pour chaque chiffre).

par **linkakro** Mar 5 Juin - 21:48

Ce n'est pas parce que des résultats semblent transcendants qu'ils sont basés sur un nombre transcendant comme pi...
L'algorithme pourrait très bien utiliser l'exponentielle e comme le nombre Pi.
Cela dit il est tout-à-fait possible que l'algorithme utilise Pi ou sa valeur approchée.

(notabene: transcendant signifie que le nombre ne peut pas être exprimé de manière littérale en fonction de réels avec des fonctions.
Et exprimer un transcendant avec des opérations ou des objet qui sont définis à partir du transcendant lui-même ne compte pas

.
Cependant il est possible d'énoncer un transcendant comme la limite d'une fonction ou d'une suite, ce qui est courant.)

par maxence Mer 6 Juin - 11:55

Finalement après avoir cherché sur internet je ne pense pas que de tels nombres soient utilisés.

En effet, si on tape "algorithme génération aléatoire" (pseudo-aléatoire), on peux trouver plusieurs sites qui expliquent comment l'aléatoire est généré grâce à des algorithmes.

D’ailleurs quelqu'un avait dit que dans les langages de bas niveaux on mesurais la vitesse du processeur, mais c'est faux, quelque soit le langage on utilise des algorithme, il en existe des tas.

Il faut savoir qu'on utilise ce qu'on appelle une "graine" pour initialiser ce genre d'algorithme, par exemple "0" dans "0→rand".

La séquence qui en résulte est en effet la même à chaque fois selon la "graine" utilisée. étonnant, mais la plupart de genre d'algorithme tiennent sur une ligne (à peine 10 caractères), et les programmeurs disent même (pour troler un peu) que plus l'algorithme utilisé est long, moins les nombres générés sont aléatoires ! Langue

Il ne reste plus qu'à savoir lequel est utilisé par les TI... (http://www.alrj.org/docs/algo/random.php)

par **linkakro** Mer 6 Juin - 16:24

C'est marrant le cycle obtenu par ax+b_mod_n.

J'aime beaucoup la méthode des xor et registres à décalages.
(cela me rappelle le cryptage de canal+ autrefois, que j'ai étudié en terminale).

par Contenu sponsorisé