MPO 95 : Balayage des rationnels

[Danny]

En effet, c'est 2 x plus rapide : 9 s pour U(500) et 12 s pour U(5000)

Mais bizarrement ça donne encore des résultats différents pour d'autres indices, par exemple :
U(5) = 85/3 au lieu de 3/2
U(10) = 3/2 au lieu de 3/5
U(25) = 177/7 au lieu de 7/5 (il est parti loin celui-là )

[C.Ret]

[...]Et c'est effectivement super rapide : 18 secondes pour U(500), 24 secondes pour U(5000) [...]U(5000) = 109/33 (au lieu de 43/162)

En effet, c'est 2 x plus rapide : 9 s pour U(500) et 12 s pour U(5000) [...]Mais bizarrement ça donne encore des résultats différents pour d'autres indices, [...]

Danny, je ne comprends pas, comment peux tu dire que le calcul est rapide ou très rapide si le résultat est faux !!??
Si l'on ne trouve pas le bon résultat, cela ne sert à rien de chronométrer, c'est faux, nous n'avons rien calculer.

Il y a là une logique que je ne comprends pas.

Tu me rappelles le temps béni où je travaillais à Marseille, la ligne de TGV fonctionnait de puis quelques semaines, un collègue fort sympathique, marseillais de bonne souche, était très fier d'annoncer à tout le monde qu'il était le plus rapide d'entre nous, un "champoing du monde" qui sera dans moins de 5h à Paris. Sauf qu'il est monté du mauvais coté de la rame qui se séparée à Avignon, il est arrivé à destination encore plus vite, en moins de 3h il était à Toulouse.


Les valeurs que tu nous donnes ne peuvent pas être atteintes avec l'algorithme de jxano. A mon avis il y a un truc que tu as oublié. Es-tu sûr de bien avoir effacer la zone programme avant de saisir le code ? J'ai essayé jusqu'à très tôt ce matin toutes les cas et je n'arrive jamais aux résultats que tu donnes.

Il va falloir que tu décortiques le code et que tu vois ce qui ne vas pas.
Prends comme exemple U(500), j'ai donné la décomposition du calcul plusieurs fois dans mes posts précédents, déroule le code que tu as saisi sur ton HP-65 pas à pas et vérifie le contenu des registres et vois si cela correspond.

A mon avis tu n'obtiens pas les bon résultat car tu as commit une erreur en saisissant le code.
Ou alors, il y a un truc spécifique sur HP-65 que j'utilise mal sans le savoir, mais là c'est à toi de m'expliquer où est mon erreur, je n'ai pas d'HP-65 fonctionnelle sous la main, c'est toi l'utilisateur

[Danny]

Danny, je ne comprends pas, comment peux tu dire que le calcul est rapide ou très rapide si le résultat est faux !!??
Si l'on ne trouve pas le bon résultat, cela ne sert à rien de chronométrer, c'est faux, nous n'avons rien calculer.

En fait il n'y a que dans le cas du U(5000) d'hier qui le résultat était faux, pour tous les autres chronos que j'ai donnés le résultat était bon.

Tu me rappelle le temps béni où je travaillais à Marseille, la ligne de TGV fonctionnait de puis quelques semaine, un collègue fort sympathique, marseillais de bonne souche, était très fier d'annonce à tout le monde qu'il était le plus rapide d'entre nous, un "champoing du monde" qui sera dans moins de 5h à Paris. Sauf qu'il est monté du mauvais coté de la rame qui se séparée à Avignon, il est arrivé à destination encore plus vite, en moins de 3h il était à Toulouse.

A mon avis tu n'obtiens pas les bon résultat car tu as commit une erreur en saisissant le code.
Ou alors, il y a un truc spécifique sur HP-65 que j'utilise mal sans le savoir, mais là c'est à toi de m'expliquer où est mon erreur, je n'ai pas d'HP-65 fonctionnelle sous la main, c'est toi l'utilisateur

Bizarre en effet, mais j'ai essayé sur la vraie HP-65 et après sur l'émulateur MultiCalc pour être sûr, et j'ai la même chose
Et de ton côté, tu testes comment la version pour HP-65 ?

[C.Ret]

Bonne nouvelle la nouvelle version est moins fausse que la première.

Je ne comprends toujours pas pourquoi ça marche pour U500 et U5000 et pas pour d'autres indices ??

Alors c'est qu'il y a un souci avec mon code et il doit y avoir un truc qui ne fonctionne pas sur HP-65 comme je l'imagine.
Je vais essayer un émulateur. Mais je suis dépité, je pensais qu'un utilisateur d'HP-65 fonctionnelle aurait sû facilement pointer du doigt l'accroc.

Sinon, mon code fonctionne à 100% sur HP-15C

Code : Tout sélectionner

001 LBL D
002   f Clear REG  STO 3  2  X<>Y  g LOG  2  g LOG  ÷  1  STO 2  +  g INT  y^x  STO 4
016   LBL 2
017      RCL 3  RCL 4  2  ÷  STO 4  g x≤y? GTO 1  g INT  g x>y? GTO 0
027 LBL A  RCL 1  R/S
030 LBL B  RCL 2  g RTN

033 LBL 0
034   RCL 1  STO+2  GTO 2
037 LBL 1
038   -  STO 3
040   RCL 2  STO+1  GTO 2

[Danny]

Alors c'est qu'il y a un souci avec mon code et il doit y avoir un truc qui ne fonctionne pas sur HP-65 comme je l'imagine.
Je vais essayer un émulateur. Mais je suis dépité, je pensais qu'un utilisateur d'HP-65 fonctionnelle aurait sû facilement pointer du doigt l'accroc.

C'est bizarre en effet... en ce moment j'ai carrément pas le temps même pour débugger, mais je ne vois rien qui pourrait déconner dans le code a priori.
Bon au pas 24 t'as mis un INT tout seul sans la touche f avant, mais j'ai supposé que c'était bien l'instruction INT qui devait être là.

[C.Ret]

Oui, c'est bien un f INT. J'ai beaucoup de mal avec le fait que ce ne soit pas mergé

Très bien fait ce simulateur/émulateur, il y a même un mode "PROGRAM TRACE" qui affiche en clair les instructions à chaque SST (ou lorsque que le programme court).

J'ai trouvé le bug, j'aurais dû y penser !

Déjà, il est dans le code commun aux deux versions, c'est à dire dans le premier tronçon juste sous le LBL D et avant les boucles principales.
Ca le fait pas avec tous les indices. Il y a comme une instabilité numérique donc.

C'est un souci d'arrondi. Evidemment c'est l'instruction y^x qui est en jeu. Sur l'HP-65 les puissances sont calculées à partir des fonctions transcendantales EXP et LN ce qui peut créer des petites erreurs d'arrondi qui ne sont visibles qu'en mettant en affichage scientifique (par exemple DSP 9) contrairement à l' HP-15C qui pour des arguments entiers fait des produits en boucle donnant un résultat entier.
L'HP-65 ne fait pas de même, il faut donc correctement arrondir à l'entier supérieur sinon on obtient des puissances de deux impaires ??!??

Par exemple 2 ENTER^ 4 g y^x affiche 16.00, mais il s'agit en fait de 15.9999999 et donc quand je divise par deux j'aggrave à chaque fois l'arrondi. Sans compter l'astuce du f INT entre les deux tests qui ne marche plus.

Voici donc une version corrigée du second programme, le premier peut être modifié de la même manière, il suffit d'appliquer le même patch au même endroit:

MPO 95 - HP-65 Calkin Wilf suite U_n using binary decomposition PATCHED.gif (29.06 Kio) Consulté 2211 fois

Danny, il faudra que tu rechronomètre car j'ai bien peur que le bugg ne faisait faire que la moitié du travail !
Sur l'émulateur je trouve 10"44 pour U(500) !
Et U(20200904) = 5057 / 18678 en 21"16 ?

[Hobiecat]

Le problème des valeurs approximatives sur les machines vintages est surtout critique au moment du calcul de la partie entière.

Je me demande dans quelle mesure il ne faut pas sur ces machines ajouter 0,001 ou équivalent pour être sûr que la partie entière soit bien 16 et non 15 dans le cas mentionné plus haut ?

[Danny]

Bien vu C.Ret, en effet les puissances de 2 ne sont pas exactes sur la HP-65, j'ai appris un truc du coup !
2^4 donne 15.99999999 comme tu l'as dit, et 2^5 donne 32.00000001 par exemple
2^10 donne 1023.99999, etc.
Les puissances paires sont en-dessous, les impaires au-dessus.

Sinon avec le patch j'ai toujours les mêmes chronos, environ 9 s pour U(500) et 12 s pour U(5000). Et 21 s pour U(20200904).

Well done !

Le problème des valeurs approximatives sur les machines vintages est surtout critique au moment du calcul de la partie entière.

Je me demande dans quelle mesure il ne faut pas sur ces machines ajouter 0,001 ou équivalent pour être sûr que la partie entière soit bien 16 et non 15 dans le cas mentionné plus haut ?

Oui en fait c'est ce qu'a fait C.Ret dans son patch: il a ajouté 0.5 (1/2).
D'ailleurs on pourrait gagner un petit pas en remplaçant 2 g 1/x par . 5 tout bêtement, a priori.

[Hobiecat]

Oui en fait c'est ce qu'a fait C.Ret dans son patch: il a ajouté 0.5 (1/2).
D'ailleurs on pourrait gagner un petit pas en remplaçant 2 g 1/x par . 5 tout bêtement, a priori.

Effectivement, j'avais raté cet ajout. Sinon, comme je l'avais proposé plus haut, EE-1 ou .1 fonctionnerait aussi, je ne pense pas que l'imprécision atteigne 0,5.

[jxano]

L'observation de la représentation en H de l'arbre de Calkin-Wilf m'a inspiré le programme suivant pour une de mes fx-880P :

10 PRINT "PARCOURS EN H ARBRE C-W": CLEAR
12 DIM P(10)
14 A=1:B=1:M=4:O$="([([([([([":F$=")])])])])]"
16 INPUT "NUMER";A,"DENOM";B,"PROF MAX";M
20 IF I=M;GOTO 30
22 B=A+B:I=I+1:P(I)=1
25 PRINT MID$(O$,M+1-I,1);
26 GOTO 20
30 PRINT STR$(A);"/";MID$(STR$(B),2);
34 IF I=M;GOTO 40
36 A=A+B:I+I+1:P(I)=2:GOTO 20
40 IF I<M;PRINT MID$(F$,M-I,1);
42 IF I=0;END
44 IF P(I)=1;I=I-1:B=B-A:GOTO 30
46 I=I-1:A=A-B:GOTO 40

Voilà, dans sa plus simple expression, un algorithme récursif (le parcours en profondeur d'un arbre binaire) sans le moindre appel récursif. Pas besoin de tableaux pour les fractions, on sait exactement comment calculer l'un des fils à partir du père et inversement, c'est la raison pour laquelle la structure porte le nom d'arbre.

Le parcours se fait depuis la fraction A/B sur M niveaux. Une paire de parenthèses enserrent un triplet fils gauche - père - fils droit, et une paire de crochets délimitent deux triplets formant les deux poteaux réunis par le barreau central du H.

Si la question de l'algorithme a rapidement trouvé une réponse, j'ai, par contre, beaucoup plus mariné sur le calage du double parenthésage. En effet, les ouvrantes et les fermantes interviennent sur des profondeurs I décalées.

[C.Ret]

[...]Oui en fait c'est ce qu'a fait C.Ret dans son patch: il a ajouté 0.5 (1/2).
D'ailleurs on pourrait gagner un petit pas en remplaçant 2 g 1/x par . 5 tout bêtement, a priori.

Oui effectivement .5 est plus court que 2 f 1/x !! A force de tester j'ai même pas vu !!

En fait, j'avais d'abord ajouté comme le suggère Hobicat 1.0E-03 , mais c'était plus long et pas assez quand l'indice n est grand il manque beaucoup.

Autre méthode, c'est de se passer des logarithmes et exponentiations. Faire tout le calcul avec les 4 opérations comme ça, même des antiquités sont (relativement) fiables. En plus c'est bien plus court, et presque aussi rapide (le calcul des LOG ou y^x est relativement lent sur ces HP Classiques).

J'en ai profité pour faire le calcul dans les deux sens :

MPO 95 - HP-65 Calkin Wilf suite U_n bijective computations.gif (37.59 Kio) Consulté 2171 fois

Le label A permet de calculer l'indice de U(n) à partir du rationnel A/B (le PGCD se trouve dans le registre R2 en fin de calcul): a [ENTER^] b (A) affiche U(n).
Le label D permet de déterminer le rationnel A/B à partir du l'indice de U(n); n [ D ] affiche A puis [SST] affiche B.

MPO 95 HP-64 Magnetic program card.gif (15.36 Kio) Consulté 2173 fois

Je voulais faire une utilisation plus sioux des cinq labels, mais il n'y a plus assez de pas de programme: l'HP-65 est utilisée à 90%

[Danny]

Magnifique

Je me demandais: les Casio récentes peuvent représenter directement des fractions je crois... personne n'est chaud pour faire une version pour une de ces japonaises ?

[jxano]

Bonne question. Je tapote sur ma fx-92 College 2D+ et je me fais les réflexions suivantes :

1/ La machine que j'ai entre les mains n'est pas programmable et je doute d'en trouver une de cette catégorie qui le soit ;

2/ Il faudrait trouver les opérations adéquates pour manipuler les nombres fractionnaires en tant que tels. Pour passer du père a/b au fils droit (a+b)/b et inversement dans l'arbre de Calkin-Wilf, il suffit d'ajouter ou de retrancher 1 au nombre. Par contre, pour le passage du père a/b au fils gauche a/(a+b), je ne vois pas trop comment faire (objet de développements futurs ?) Pour le parcours du Stern-Brocot, je ne vois pas trop comment faire assimiler la "somme du cancre" (pour le calcul des médianes) à ces machines...

Personnellement, manipuler les fractions sous la forme d'un couple d'entiers me convient très bien.

[C.Ret]

L'observation de la représentation en H de l'arbre de Calkin-Wilf m'a inspiré le programme suivant pour une de mes fx-880P :

[ ... captured BASIC code into a CBM 128D ... ]

[...]
Si la question de l'algorithme a rapidement trouvé une réponse, j'ai, par contre, beaucoup plus mariné sur le calage du double parenthésage. En effet, les ouvrantes et les fermantes interviennent sur des profondeurs I décalées.

Excellente algorithme, je n'ai seulement compris pourquoi jxano c'est donné tant de mal pour alterner parenthèses et crochets que lorsque j'en suis arrivé à une représentation en 2D !
C'est effectivement primordiale, dans l'exemple ci-dessous, les parenthèses rassemblent les éléments selon la partie verticale du H, alors que les crochets correspondent aux parties horizontales :

Bien joué en tout cas !

MPO 95 C128D jxano Calkin Wilf H-Tree on 80 col..gif (7.54 Kio) Consulté 2132 fois

J'ai mis du vert et du mauve pour mieux voir la correspondance, je ne sait pas si ça ce voit bien ?

Est-ce que tout le monde voit bien les sept H ?

[jxano]

Eh bien voilà ! J'en ai rêvé très fort, C.Ret l'a fait ! Avec beaucoup d'espaces entre les nombres et les caractères semi-graphiques en T qui vont bien.

J'ai écrit une seconde version (dans le même zone de programme) qui "dessine" l'arbre sur cinq niveaux ; c'est un peu plus serré dans les sept lignes virtuelles de la Casio, mais les 31 valeurs tiennent dedans, avec deux chiffres possibles par entier. Le code n'a pas vraiment d'intérêt.

Au reste, dans mon premier code pour 880P, je m'aperçois que je peux me passer du tableau P(), car on sait toujours si on est fils gauche ou fils droit en remontant à la fin, en testant l'ordre entre numérateur et dénominateur. Cela ouvre la voie à des machines plus vénérables pour mon algorithme.

Tu as finalement repris la disposition des valeurs en 1/n et n/1 du dessin du début de la page 4 du présent fil de discussion, en colimaçon et en miroir par rapport à la verticale, malgré la petite remarque que tu fais juste après. Je suis plus à l'aise en disposant ces valeurs en escalier d'un coin à l'autre du graphique.