MPO 95 : Balayage des rationnels

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Répondre
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: MPO 95 : Balayage des rationnels

Message par Danny »

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

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à :geek:)
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO 95 : Balayage des rationnels

Message par C.Ret »

Danny a écrit : 03 sept. 2020 19:55[...]Et c'est effectivement super rapide : 18 secondes pour U(500), 24 secondes pour U(5000) 8)[...]U(5000) = 109/33 (au lieu de 43/162)
Danny a écrit : 04 sept. 2020 11:48En 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 :)
Modifié en dernier par C.Ret le 04 sept. 2020 22:06, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: MPO 95 : Balayage des rationnels

Message par Danny »

C.Ret a écrit : 04 sept. 2020 18:13 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.
C.Ret a écrit : 04 sept. 2020 18:13 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.
:lol:
C.Ret a écrit : 04 sept. 2020 18:13 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 ?
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO 95 : Balayage des rationnels

Message par 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
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: MPO 95 : Balayage des rationnels

Message par Danny »

C.Ret a écrit : 04 sept. 2020 18:46 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à.
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO 95 : Balayage des rationnels

Message par 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
MPO 95 - HP-65 Calkin Wilf suite U_n using binary decomposition PATCHED.gif (29.06 Kio) Vu 5958 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 ?
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3626
Enregistré le : 06 sept. 2011 14:57
Localisation : Normandie

Re: MPO 95 : Balayage des rationnels

Message par 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 ?
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: MPO 95 : Balayage des rationnels

Message par 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 ! 8O
2^4 donne 15.99999999 comme tu l'as dit, et 2^5 donne 32.00000001 par exemple :mrgreen:
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 !
Hobiecat a écrit : 05 sept. 2020 11:35 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.
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3626
Enregistré le : 06 sept. 2011 14:57
Localisation : Normandie

Re: MPO 95 : Balayage des rationnels

Message par Hobiecat »

Danny a écrit : 05 sept. 2020 12:00 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. :wink:
jxano
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2362
Enregistré le : 16 févr. 2008 23:34
Localisation : Paris 20ème

Re: MPO 95 : Balayage des rationnels

Message par 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.
Programmeur abscons.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO 95 : Balayage des rationnels

Message par C.Ret »

Danny a écrit : 05 sept. 2020 12:00 [...]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 !! :o

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
MPO 95 - HP-65 Calkin Wilf suite U_n bijective computations.gif (56.37 Kio) Vu 1867 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
MPO 95 HP-64 Magnetic program card.gif (15.36 Kio) Vu 5920 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%
Modifié en dernier par C.Ret le 03 août 2022 08:47, modifié 2 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: MPO 95 : Balayage des rationnels

Message par 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 ? :geek:
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
jxano
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2362
Enregistré le : 16 févr. 2008 23:34
Localisation : Paris 20ème

Re: MPO 95 : Balayage des rationnels

Message par 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.
Programmeur abscons.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO 95 : Balayage des rationnels

Message par C.Ret »

jxano a écrit : 05 sept. 2020 23:16 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
MPO 95 C128D jxano Calkin Wilf H-Tree on 80 col..gif (7.54 Kio) Vu 5879 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 ?
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
jxano
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2362
Enregistré le : 16 févr. 2008 23:34
Localisation : Paris 20ème

Re: MPO 95 : Balayage des rationnels

Message par 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.
Programmeur abscons.
Répondre

Retourner vers « Tous les Pockets »