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
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 »

Explication :

La suite définie récursivement par Image et Image avec Image permet effectivement de répertorier tous les rationnels.

Les 32 premiers rationnels répertoriés par cette suite sont les suivants :

Code : Tout sélectionner

U(n) = a_n / b_n
      n   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

     a_n  1  1  2  1  3  2  3  1  4  3  5  2  5  3  4  1  5  4  7  3  8  5  7  2  7  5  8  3  7  4  5  1...
U-n= ─── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ── ──    
     b_n  1  2  1  3  2  3  1  4  3  5  2  5  3  4  1  5  4  7  3  8  5  7  2  7  5  8  3  7  4  5  1  6...


En effet cette suite parcourt en largeur l'arbre de Calkin-Wilf qui est en bijection avec l'ensemble (infini) des rationnels strictement positifs. Cet arbre ressemble à l'arbre de Stern-Brocot qui lui aussi permet de répertorier tous les rationnels mais d'une autre façon. Les deux arbres se ressemblent énormément, seul l'ordre des rationnels au sein de chaque niveau change. Mais ce sont les mêmes éléments.

Image
(j'aime bien cette façon de faire pour dessiner l'arbre, mais à chaque nœud, j'aurais tourné dans l'autre sens en mettant le rationnel le plus petit à gauche et le plus grand vers la droite. C'est un détail.
Il manque deux niveaux, on ne voit sur cette figure que le grand-père de U(500) c'est à dire U(125) ! Vous l'avez trouvé ?)



Ce qui est pratique et explique la plupart des propriétés curieuses de cette séquence est que l'arbre de Calkin-Wilf (comme celui plus ancien de Stern-Brocot) est un arbre binaire. C'est à dire qu'à chaque rationnel Image est associé exactement deux autres rationnels fils, l'un plus petit et l'autre plus grand.


Image

C'est une idée simple et géniale ; pour tout élément Imagede l'arbre,
le fils situé à gauche (celui de valeur plus faible que U(n)) sera Image,
le fils situé à droite (celui de valeur plus fort que U(n) ) sera Image

En le construisant de cette façon, l'arbre contiennent tous les rationnels positifs irréductibles. Comme il s'agit d'un arbre binaire, les indices de la suite le parcourant en largeur (pas trop le choix en fait ; difficile de parcourir en profondeur un arbre de dimension infinie !) donne la position dans l'arbre.

On peut donc construire l'arbre de proche en proche, ce qui revient à la méthode brute qui consiste à calculer tous les U(n) jusqu'à arriver à U(500).

la définition des fils par a rapport au dénominateur et numérateur de leur père fait que cette suite U(n) se construit à partir d'une séquence particulière Fusc(n) (Suite de Sterne), la même en fait que celle de l'autre arbre. C'est la façon dont on a défini les deux fils de chaque rationnel de l'arbre qui explique pourquoi le dénominateur du premier est le numérateur du suivant. Et comme l'autre partie de la fraction s'obtient par l'addition de termes consécutifs, cette séquence contient du Fibonacci et du triangle de Pascal, ce qui explique sa curieuse définition récurrente.

Mais l'on peut aussi déduire de la décomposition binaire de n quelle est sa position dans l'arbre. A partir de ce point deux stratégies peuvent être utilisées pour déterminer U(n),
* soit on refait le calcul jusqu'à revenir à la racine, par exemple à l'aide de combinaison de matrices (cf. code post précèdant),
* soit on utilise un propriété des fractions continues.

Tous les rationnels ont un développement en fraction continue fini (contrairement aux nombres réels, nombres transcendantaux et irrationnels).
Et justement, l'arbre de Calkin-Wilf (comme en partie l'arbre de Sterne-Brocot) a été construit de façon à simplifier au maximum la relation entre le développement de chaque rationnel père avec les développements de ses deux fils. D'un terme à l'autre de l'arbre, il y a des inversions et des additions entre numérateur et dénominateur. C'est exactement les opérations que l'on effectue lorsque l'on essaye de simplifier l'écriture d'une fraction continue.

Punaise je vais de découvertes en découvertes, qu'est-ce c'est con les maths !! :)


La racine de l'arbre binaire de Calkin-Wilf commence à Image.
La racine est le seul élément présent dans le premier niveau de l'arbre.
Le second niveau sera donc constitué des deux rationnels fils issus de la racine U(1)=1 dont les indices seront respectivement et 2 et 3.
Le troisième niveau sera donc constituer de 4 rationnels (les deux fils des deux éléments du niveau 2) et seront respectivement d'indice 4,5,6 et 7
Le quatrième niveau commence à 8, le cinquième à 16, et ainsi de suite ...

Par exemple:
Sur le quatrième niveau commençant à l'indice 8, et qui est composé de huit rationnels { 1/4 4/3 3/5 5/2 2/5 5/3 3/4 4/1 }, les quatre premiers sont les fils (alternés petit et grand) des deux premiers rationnels du niveau précèdent { 1/3 3/2 2/3 3/1 }. La parité de l'indice (le bit b0) indique s'il s'agit d'un rationnel inférieur à l'unité (indices pairs) ou supérieur à l'unité (indices impairs). la rationnel 3/5 d'indice 10 est un rationnel inférieur à 1, c'est le troisième rationnel du quatrième niveau (position lue sur les premiers bits + 1).
Son père U(5) est au troisième niveau 5=%101b avec un indice impair (b0=1) il est donc plus grand que l'unité et se trouve en seconde position (deux dernier bit de n + 1) . Son grand-père est U(2) d'indice pair donc 1/2 < 1 premier des deux frères du seul groupe de ce niveau. Et son arrière-grand-père n'est rien d'autre que la racine U(1)=1/1.
L'indice est en quelque sorte sont héritage, c'est le code "génétique" qui décrit sa filiation, sa parité (dont s'il est <1 ou 1>) c'est à dire s'il est rattaché à la branche de gauche ou de droite de l'arbre.
U(10) 3/5 %1010b quatrième niveau, troisième position, cadet <1, branche de gauche
U(5) 3/2 %101b troisième niveau, seconde position, ainé 1> , branche de droite
U(2) 1/2 %10b second niveau , première position, cadet <1 , branche de gauche
U(1) 1/1 %1b racine qui n'a pas de code génétique i=%1b car le dernier bit du code indique simplement que l'on a commencé à compter à 1 (ce qui l'air de rien est un détail important qui permet de lire le code génétique , c'est à dire la position de u(n) dans l'arbre sans avoir à se préoccuper de retenues).

Image

Vous comprenez la relation intime qu'il y a dans la séquence énumérant les rationnels, leur indice dans la suite U(n), la décomposition binaire de l'indice n, la position géographique de U(n) dans l'arbre et les propriétés du rapport a_n/b_n dont les numérateur et dénominateurs sont lié d'une branche à l'autre ?

Image

C'est pure magie !

Ah! Oui vous aviez pas vu que les éléments de la suite proposé par gégé sont une alternance de rationnels inférieurs à 1 et supérieurs à 1. Le nombre de propriétés remarquables concernant ces arbres et ces suites est tout simplement hallucinant. Pour moi qui aime l'ordre , la symétrie, les nombres et les transformations, je suis en plein dans la matrice, je cours comme un fou après le lapin blanc au pays rêvé d'Alice.

L'algorithme basé sur les matrices, utilise un codage astucieux de chaque rationnel à l'aide d'une matrice carré 2x2 reprenant les numérateur et dénominateur des deux rationnels générateur. Oui, j'ai pas expliqué, mais pour être sûr que l'arbre (ou la suite) ne contienne qu'une seule fois chaque rationnel strictement positif sous sa forme irréductible, on utilise des suites de Farey et chaque rationnel est en réalité obtenu par une médiane entre deux points asymptotiques P2 et P1 qui ne peuvent faire partie de l'arbre (ou de la suite); A savoir vers la gauche la valeur zéro (matrice 0/1) et à droite l'infini (qui est exprimé sous la forme curieuse 1/0). La racine de l'arbre est exactement placée au milieu, sur la médiane Image.
Avec les matrices, La racine U(1)=1/1 est représentée par la matrice identité Image il est possible de calculer la valeur de U(n) en suivant le chemin au travers de l'arbre à l'aide d'une matrice de passage selon que l'on suit la branche de gauche (vers le plus petit des fils) ou la branche de droite (vers le plus grand des fils) à l'aide de deux matrices de passage respectivement G et D qui permettent de calculer la matrice représentant la nouvelle médiane du rationnel fils.
Mais il faut répéter l'opération à chaque niveau, toujours selon que l'on va vers la droite (vers l'infini) ou la gauche (vers le néant), c'est ce que fait le code d'avant-hier.
Pour calculer U(500), c'est plus rapide que de calculer les 499 éléments de la suite de Stern. Comme U(500) n'est pas très loin, il est quelque part au 9-ième niveau de l'arbre (en effet 500=%111110100b fait 9 bits de long).

Avec lecalcul utilisant les fractions continues, ce n'est plus les directions droite ou gauche qui entrent en jeu, mais le nombre de fois que l'on continue dans la même direction. Chaque fois que l'on change de direction, on effectue une inversion en plus de l'addition des termes. Quand on continue dans la même direction ne fait qu'additionner numérateur et dénominateur.
Ce qui fait que pour, par exemple, 500=% 11111 0 1 00 b est composé de 4 groupes de bits consécutifs identiques, il n'y a que quatre changement de direction gauche/droite. c'est donc encore plus court !

gégé a toujours de bonnes questions, je suis sûr qu'il connait tout cela par cœur et que c'est pour cela qu'il à propose cette suite U(n) !?
Quel magicien ! Quel guide d'agence de voyage rationnel infinitésimal multidimensionnel.

Par exemple, pour calculer U(500):
Image

Et pour U(5000):
Image

Et pour calculer U(1081):
Image


D'où le code pour SHARP PC-1211:

Code : Tout sélectionner

1:CLEAR :INPUT N:B=1,D=2^INT (LOG N/LOG 2
2:R=1-R,F=A
3:IF D IF INT (N/D)=R LET N=N-RD,D=INT .5D,F=F+B:GOTO 3
4:A=B,B=F:IF D+R GOTO 2
5:BEEP 1:PRINT A,B
RUN[ENTER] 500 [ENTER] affiche 11. 28. en 10"67.

Registres:
N valeur de l'indice, pendant la décomposition la valeur de D est retirée de N pour tous les bits à 1.
D valeur binaire servant à décomposer l'indice; je fais varier D de 2^p à 0 par division par 2 avec p=INT(LOG2(N)).
Dans ce sens la décomposition et le calcul des fractions continues est plus facile.
R bit du groupe, comparé à INT(N/D)=R afin de compter la taille t des groupes de bits consécutivement à 1 ou 0
F calcul de la fraction continue. Chaque fois qu'un bit est compté, F est incrémenté de B
A/B registres contenant le rationnel U(N)=A/B, à chaque changement de groupe de t-bits les valeurs de A et B sont échangées F=A,A=B,B=F
En réalité ce revient à effectuer l'inversion et les additions A'←B, B'←A+t.B où t est le nombre de bits identiques.

Touts les bits sont testés (D est divisé par deux jusqu'à D=0). Lorsque D=0, les indices impairs sont détectés par R=1 (les indices pairs finissent avec R=0 lorsque D s'annule).
Le test D+R permet alors un tour de boucle supplémentaire qui inversera le rapport A/B afin d'obtenir U(n)=A/B plus grand que l'unité.
L'addition est utilise, le PC-1211 n'a pas d'opérateur OR.


Je suis en train de préparer la version pour HP-65 :)


EDIT:
Pas facile pour moi de faire un truc court sur cette machine:
MPO 95 - HP-65 Calkin Wilf suite U_n using binary decomposition and continous fractions algo.gif
MPO 95 - HP-65 Calkin Wilf suite U_n using binary decomposition and continous fractions algo.gif (64.88 Kio) Vu 6381 fois
Registres:
R5:N valeur de l'indice, pendant la décomposition la valeur de D est retirée de N pour tous les bits à 1.
R4:D valeur binaire servant à décomposer l'indice D varie de 2^p à 0 où p est N log 2 LOG / INT
R3:R bit de groupe, comparé à INT(N/D)=R afin de compter la taille des groupe de bits consécutivement à 1 ou 0
R2:B
R1:A A/B registres contenant le rationnel U(N)=A/B, à chaque changement de groupe de t bits les valeurs de A et B sont échangées

Il n'y a pas de registre pour F, les incréments de B sont directement effectués dans A. Et l'échange se fait directement par l'intermédiaire de la pile entre R1:A et R2:B

Utilisation:
Saisir n et presser sur D pour lancer la détermination. A la fin du calcul le numérateur A est affiché, pressez R/S pour voir le dénominateur B.
Les labels A et B permettent d'afficher directement le numérateur A et le dénominateur B.

Le programme est long, il y une cinquantaine d'instructions qui ne sont pas toutes mergées, tout cela occupe 83 des 100 pas de programme disponibles. C'est moche pour un MPO. J'ai été surpris d'apprendre que même les pressions sur la touche préfixe 'f' sont enregistrées et comptent. Du coup, 100 pas sur cette machine, ce n'est pas énorme.
Mais c'est suffisant, elle a servie pour voyager jusqu'à la Lune, alors ce doit être bien.

Je compte sur les experts en machine classique pour améliorer ma piètre performance. Heureusement que certains lecteurs/enregistreurs de cartes magnétiques fonctionnent encore ! Danny aura peut-être la chance de ne pas avoir à tout retaper à chaque utilisation :)


Sur le listing, les nombres à trois chiffres sont les numéro de pas du programme jumeaux pour HP-15C. Je n'ai pas de HP-65 et donc j'ai utilisé mon HP-15C pour éprouver ce code. Avoir les cross-références sous les yeux peut être utile. En plus cela m'agace de ne pas avoir de n° d'instruction ce qui peut rendre d'éventuels remarques, notes ou commentaires concernant le code difficiles.

Je ne sait pas combien de temps met le calcul de U(500) avec ce programme. Pas sûr qu'il soit si rapide que cela. 81 instruction c'est beaucoup.



Ci-dessous le code pour HP-15C. Les registres sont exactement les mêmes. Mais dans ce code tout est mergé, presque à outrance.
MPO 95 - HP-15C Calkin Wilf suite U_n using binary decomposition and continous fractions algo.gif
MPO 95 - HP-15C Calkin Wilf suite U_n using binary decomposition and continous fractions algo.gif (63.68 Kio) Vu 6381 fois
500 f-D affiche 11 [R/S] 28 au bout de 24"23 sur une HP-15C lente mais vigoureuse.
5000 f-D donne 43 [R/S] 162 en moins de 42"
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
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 »

gege a écrit : 22 août 2020 02:05 ...
Points additionnels à celui qui trouve U(5000)...
...
Je suis prêt à céder mes points à Danny s'il trouve U(500) sur sa merveilleuse HP-65 qui fonctionne comme une neuve ou à Hobiecat qui calcule U(5000) sur une HP-41C.

Je veux juste savoir ce que je gagne à calculer U(202008311856)= 420194 / 1872781 en 4"33 sur mon HP-28S en utilisant ce code RPL:

Code : Tout sélectionner

« 1 SF 0 1 ROT 2 OVER LOG 2 LOG / IP ^         //  Initialise bit de groupe (Flg n°1) a b n d=2^p avec p=INT(LOG2(n))
  DO                                           //  **** BOUCLE PRINCIPALE *****
     IF DUP2 >= 1 SF? ==                       //     SI Bit de groupe == Flg n°1 
         THEN                                  //     ALORS
            IF 1 FS? THEN SWAP OVER - SWAP END //        SI bit de groupe à 1 ALORS n←n-d (cas n>=d)
            2 / IP                             //        divise d par 2 
            4 ROLL 4 PICK + 4 ROLLD            //        ajoute dénominateur b au numérateur a
         ELSE                                  //     SINON  
            IF 1 FC?C THEN 1 SF END            //        change l'état du bit de groupe  1←→0  
            ROT 4 ROLLD END                    //        échange a et b 
  UNTIL DUP NOT END                            //  **** Boucle jusqu'à d==0  
  DROP2                                        //  efface n et d, il reste a et b 
  IF 1 FC? THEN SWAP END »                     //  inverse a et b si bit de groupe indique un n impair


Espérant gagner un bon point, j'ai fait cette fois l'effort de bien indenter mon listing. Et même de le commenter. L'algorithme est exactement celui pour SHARP PC-1211 et HP-65 comme expliqué dans mon précèdent post. Avec cependant le bit de groupe mémorisé par l'état du flag binaire n°1 et l'échange entre numérateur et dénominateur se fait simplement par une simple instruction SWAP finale.

U(500)=11/28 est 1"60 et U(5000)= 43/162 en 2"1

Vous remarquerez que tout ce fait sur 4 niveaux de pile opérationnelle comme s'il l'on était en RPN :) :)
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 »

Cela fait un bout de temps que je ne m'étais pas intéressé à un MPO...

Après étude des propos de C.Ret et de quelques fiches Wikipedia, j'ai remis des piles fraîches dans mon Casio fx-790P (l'exemplaire "historique" rafistolé au ruban adhésif havane...) et j'ai pondu quelques petits programmes, histoire d'éclairer le sujet sous des angles un peu différents.

Pour commencer, C.Ret a parlé quelque part de fonction récursive pour le calcul de la suite Fusc. Dans le cas simple d'un seul appel récursif, on peut reproduire les variables locales et les retours de fonction par des tableaux jumelés. Le tableau A() regroupe les résultats des divisions par deux de l'indice N jusqu'à 1, la clause d'arrêt. C() et D() reprennent les Fusc(n) et Fusc(n+1) calculés à rebours, "en sortie de fonction".

10 PRINT "FUSC AVEC TABLEAUX": CLEAR
12 DIM A(30),C(30),D(30)
20 INPUT "INDICE",N
22 I=0:A(0)=N
30 IF A(I)=1;C(I)=1:D(I)=1: GOTO 40
32 A(I+1)= INT(A(I)/2)
34 I=I+1: GOTO 30
40 I=I-1: IF I<0; GOTO 50
42 IF FRAC(A(I)/2)=.5; GOTO 46
43 C(I)=C(I+1):D(I)=C(I+1)+D(I+1)
44 GOTO 40
46 C(I)=C(I+1)+D(I+1):D(i)=D(I+1)
47 GOTO 40
50 PRINT "FUSC("; STR$(N);")=";C(0)
52 GOTO 20

L'arbre de Stern-Brocot contient les fractions dans l'ordre numérique, niveau après niveau. Dans une page Wikipedia, on parle de "somme du cancre" pour calculer les fractions à partir de deux autres. J'ai imaginé l'énumération des rationnels de zéro (0/1) à l'infini (1/0) sous forme d'une liste chaînée, rangés tous ensemble, quelque soit le niveau. Chaque parcours de celle-ci calcule et affiche un étage supplémentaire de l'arbre.

10 PRINT "ARBRE DE STERN-BROCOT": CLEAR
12 INPUT "NBR NOEUDS (<256)",T
14 DIM M(T),N(T),S(T)
16 S(0)=1:M(0)=0:N(0)=1
17 S(1)=-1:M(1)=1:N(1)=0
19 I=1
20 I=I+1: IF I>T; PRINT " F": END
22 S=S(C)
24 M(I)=M(C)+M(S):N(I)=N(C)+N(S)
26 S(C)=I:S(I)=S
28 PRINT M(I);"/"; STR$(N(I));
30 IF N(S)=0; PRINT "*":C=0: GOTO 20
32 C=S: GOTO 20

Dans une autre page Wikipedia, j'ai vu les fractions de l'arbre de Calkin-Wilf arrangées en escargot, toutes reliées à 1/1 formant le centre. Pour chaque fraction, le programme en calcule deux autres et donne le chemin complet jusqu'au centre.

10 PRINT "ARBRE DE CALKIN-WILF": CLEAR
12 INPUT "NBR NOEUDS (<256)",T
14 DIM M(T),N(T),P(T)
16 M(0)=1:N(0)=1:P(0)=-1
20 I=I+1: IF I>T; END
22 M(I)=M(C):N(I)=M(C)+N(C):P(I)=C
24 D=I: GOSUB 40
30 I=I+1: IF I>T: END
32 M(I)=M(C)+N(C):N(I)=N(C):P(I)=C
34 D=I: GOSUB 40
36 C=C+1: GOTO 20
40 IF D=-1; PRINT "": RETURN
42 PRINT M(D);"/"; STR$(N(D));
44 D=P(D): GOTO 40
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 : 31 août 2020 21:19...Pour commencer, C.Ret a parlé quelque part de fonction récursive pour le calcul de la suite Fusc...
Ah! Je suis content de voir que même rafistolée de bout de scotch, cette CASIO fonctionne toujours.

J'avais effectivement deux projets;
* l'un consistait à calculer simultanément Fusc(n) et Fusc(n+1)
* l'autre à trouver un moyen de calculer Fusc() sans appels récursifs afin de la faire facilement sur un pockets n'aimant pas la récursivité.

Et voilà que le premier programme de Jxano propose une solution astucieuse qui fait les deux choses en une seule passe !

Notons qu'en recopiant, jxano a dû oublier une partie de la ligne 50 qui affiche Fusc(n) car elle devrait contenir aussi l'affichage de Fusc(n+1):
50 PRINT "FUSC("; STR$(N);")=";C(0) : PRINT "FUSC("; STR$(N+1);")=";D(0)

J'ai trouvé ce code fort astucieux, et il prend effectivement le contre-pied de la stratégie que j'utilise. je voulais déterminer les valeurs des Fusc() afin de calculer les rationnels U(n) de la séquence demandée par gégé.
Son programme fait exactement l'inverse, pour calculer les Fusc(), il utilise la relation qui existe entre deux rationnels selon la parité de leur indice Image et Image .

On peut donc ajouter la ligne supplémentaire à son programme qui non seulement calcule les deux ternes consécutifs de la suite de Stern , mais auusi le rationnel de la séquence pour gégé :
51 PRINT "U(";STR$(N);") = "; STR$(C(0));"/";STR$(D(0));"."

Je trouve cette méthode fort astucieuse et efficace, je m'empresse de la saisir sur mon tout nouveau SHARP 1280 (merci à Rémy)

Code : Tout sélectionner

10:"Z" CLEAR : DIM N(30)
20:I=0,A=1,B=1: INPUT "n=";N(0)
30:IF N(I)>1 LET I=I+1,N(I)= INT (N(I-1)/2): GOTO 30
40:IF I LET I=I-1,A(2-(N(I) AND 1))=A+B: GOTO 40
50:PRINT "U"+ STR$ N(0)+"=", STR$ A+"/"+ STR$ B
52:GOTO 20
Quelques remarques concernant ce dernier code:
  • - il s'agit très exactement de l'algorithme de Jxano, j'ai même volontairement conservé les numéros de ligne afin de bien mettre en correspondance chaque étape.
  • - Le test FRAC(N(I)/2)=.5 est remplacé par une astuce plus simple en utilisant l'opérateur AND pour tester le bit de poids faible. Ainsi, N(i) AND 1 renvoi 1 pour les N(i) impairs et 0 pour les N(i) pairs.
  • - il n'y a plus les tableaux A() ou B(). En effet, le code original était basé sur les affectations A(i-1)=A(i), B(i-1)=B(i), A(i-1)=A(i)+B(i) ou B(i-1)=A(i)+B(i). J'ai un peu simplifié (nous sommes dans un MPO c'est un peu le but de ce sport) en utilisant des affectations A=A, B=B , A=A+B ou B=A+B. Je me suis très vite rendu compte que les affectations A=A et B=B ne servent à rien. Ce qui fait qu'en fonction de la parité des N(I) on a soit A=A+B, soit B=A+B.
  • - il n'y a pas sur ce SHARP de structure IF...THEN...ELSE...END, et donc mon idée d'utiliser IF N(i) AND 1 THEN A=A+B ELSE B=A+B END ne marche pas. Par contre, sur ce SHARP PC1280, comme pas mal d'autres chez SHARP comme les PC1350, PC1360, PC????, les registres simples A,B,C,...,Z correspondent également aux éléments du tableau A(). Ceci afin d'être compatible avec les codes issus de l'ancêtre commun SHARP PC1211 qui n'a pas d'instruction DIM et dont c'est là le bien seul et bien maigre moyen d'avoir des tableaux.
  • - L'affectation étrange A(2-(N(i) AND 1)=A+B revient donc à faire A=A+B pour les N(i) impairs et B=A+B pour les N(i) pairs car les registres A et B sont également les éléments A(1) et A(2).
MPO 95 PC-1280 U500 11 28.png
MPO 95 PC-1280 U500 11 28.png (51.45 Kio) Vu 6303 fois
Le SHARP PC1280 mets 2" pour calculer U500 avec ce code.
Modifié en dernier par C.Ret le 01 sept. 2020 21:02, 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
Ythunder
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 4549
Enregistré le : 09 août 2008 17:46
Localisation : 03

Re: MPO 95 : Balayage des rationnels

Message par Ythunder »

Je suis impressioné, mais je préfère le mode 320x200 avec contrainte de proximité de mon TO7-70...
Quand je lis ça "oui des passionnées qui modifie des machines pour en faire des moutons a 5 pattes qui n'ont plus rien a voir avec la machine d'origine afin de faire la video choc sur youtube..."

Ca me fait rire. Perso, je n'ai ni chaine youtube sur les machines et je n'ai aucun mouton à 5 pattes qui n'a pàlus rien a voir avec des machines d'origine. Mais à qui s'adressait on ?
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 »

J'ai trouvé quelque chose d'intéressant.

J'ai rêvassé un peu longtemps sur la représentation en H des 7 premiers niveaux de l'arbre de Calkin-Wilf en me demandant s'il y avait une façon pratique de numéroter les sommets. La racine 1/1 est le numéro 1, et j'ai pensé ajouter 0 pour le successeur inférieur à 1, et 1 pour l'autre, en représentation binaire. J'ai modifié le troisième code de mon message précédent pour que le tableau P() me donne les numéros en décimal (P(I)=2*P(C) en 22 et P(I)=2*P(C)+1 en 32), et j'ai fait tourner le programme jusqu'à 125, qui me donnait 11/6. J'ai pensé : mh, ça sent bon.

Après quelques tâtonnements, j'ai produit le code suivant :

10 PRINT "Un PAR CALKIN-WILF": CLEAR
12 DIM A(30)
20 INPUT "INDICE",A(0):I=0
30 IF A(I)=1;M=1:N=1: GOTO 40
32 I=I+1:A(I)= INT(A(I-1)/2): GOTO 30
40 I=I-1: IF I<0; GOTO 50
42 IF FRAC(A(I)/2)=.5; GOTO 46
44 N=M+N: GOTO 49
46 M=M+N
49 GOTO 40
50 PRINT "U("; STR$(A(0));")=";M;"/"; STR$(N)
52 GOTO 20

J'ai eu un doute sur les indices des sommets des deux arbres en pensant qu'au pire, il y avait une clé pour passer d'un système à l'autre ; en fait non, c'est direct. En vérifiant par cohérence avec mes autres programmes, je trouve bien U(500)= 11/28 et U(5000)= 43/162.

C.Ret, j'ai vu passer ton message... et je ne crois pas que la simple modification de mon premier code le fait marcher comme tu le penses. Il faut bien relancer le programme pour chaque indice.
Programmeur abscons.
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 »

Ythunder a écrit : 01 sept. 2020 19:13 Je suis impressioné, mais je préfère le mode 320x200 avec contrainte de proximité de mon TO7-70...
J'aimerais bien avoir aussi un mode graphique accessible et facilement programmable pour naviguer un peu dans le Calkin-Wilf en H...

J'ai vérifié sur le programme de calcul de Fusc : effectivement, D(0) donne bien le Fusc(n+1). Cela dit, le programme est bien conçu pour la définition du Fusc, avec à chaque niveau de quoi faire l'addition en cas d'indice impair.

Dans le parcours du Calkin-Wilf, j'ai pensé que chaque descente ne nécessite rien d'autre qu'un numérateur et un dénominateur, seuls utiles pour faire la petite addition qui va bien... donc plus besoin de tableaux !

Il y a sans doute similitude de structures. Dans mon cheminement de pensée, j'ai dû déjà atteindre le sommet sans m'en rendre compte, avant d'y retourner par une autre voie.
Programmeur abscons.
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 »

Si la descente en profondeur dans l'arbre est aisée, la remontée l'est tout autant : pour chaque fraction n/d irréductible formant un noeud, on peut toujours déterminer s'il est le fils gauche ou droit de son père (par le fait que la fraction est inférieure ou supérieure à 1, n<d ou n>d), et calculer ce dernier : n/(n-d) ou (n-d)/d. En suivant la convention que je me suis donnée pour le calcul de U(n), je peux déduire l'indice en tapant la fraction :

10 PRINT "INDICE DANS ARBRE C-W": CLEAR
12 DIM A(30)
20 INPUT "NUMER",N,"DENOM",D:I=0
30 IF N=1; IF D=1;R=1: GOTO 40
32 IF N>D;A(I)=1:N=N-D: GOTO 34
33 D=D-N:A(I)=0
34 I=I+1: GOTO 30
40 I=I-1: IF I<0; GOTO 50
42 R=2*R+A(I): GOTO 40
50 PRINT "RES=";R: GOTO 20

Dans les premiers essais du programme, je souhaitais retrouver l'indice de 43/162. J'obtenais 7340024 au lieu de 5000... bizarre. Après vérification, je me suis rendu compte que j'avais tapé 53 au numérateur. En entrant le résultat faux dans l'autre programme, j'ai bien retrouvé mon erreur : 53/162.

Comme précédemment, on conserve le principe d'appels récursifs avec clause d'arrêt en faisait un aller et un retour. Pour calculer juste un nombre, on pourrait ne faire qu'une passe... C'est oublier le fait qu'il faudrait commencer par les grandes puissances de 2 dont on ne connaît pas l'ordre a priori.
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 : 01 sept. 2020 20:34[...]J'ai vérifié sur le programme de calcul de Fusc : effectivement, D(0) donne bien le Fusc(n+1). Cela dit, le programme est bien conçu pour la définition du Fusc, avec à chaque niveau de quoi faire l'addition en cas d'indice impair.[...]
Et oui, en le parcourant, j'avais trouvé ton programme très intéressant et comme c'est du bon BASIC, je l'ai immédiatement tapé sur mon Commodore C128D tel quel. J'ai vu qu'il fonctionnait très bien alors j'ai ajouter quelques PRINT intermédiaires pour pister le contenu des tableaux au fur et à mesure de son avancement. Et comme tu l'avais très clairement expliqué dans ton post, C() et D() contiennent effectivement Fusc(n) et Fusc(n+1).
Et donc ton code permet aussi de calculer U(n).
jxano a écrit : 02 sept. 2020 10:20[...]je peux déduire l'indice en tapant la fraction :[...]
Encore un projet où tu me devance. Effectivement, trouver un moyen de faire l'exercice inverse et tout aussi intéressant. L'astuce de comparer numérateur n et dénominateur d afin de déterminer quelle branche de l'arbre on remonte est tout simplement géniale.

Je vois cependant un petit inconvénient à ton code, l'arbre de Calkin Wilf ne contenant que des rationnels sous leur forme irréductible, que se passe-t-il si l'on entre des numérateurs et dénominateurs non premier entre eux ?

Voici, basé sur ton algorithme, ma version qui gère les cas où l'utilisateur n'entre pas une fraction irréductible:

Code : Tout sélectionner

10 input "ENTER rational A/B  A,B = ";a,b
20 if abs(a)<>int(a) or abs(b)<>int(b) or b=0 then stop
30 i=0:p=.5:print a;"/";b;" = ";
40 p=2*p:if a<b then b=b-a:goto 40
50 if a>b then a=a-b:i=p+i:goto 40
60 i=i+p:if a>1 then print a;"* ";
70 print "U(";i;")"
Par exemple :

Code : Tout sélectionner

run
ENTER rational A/B  A,B = ? 11,28
 11 / 28  = U( 500 )

ENTER rational A/B  A,B = ? 33,84
 33 / 84  =  3 * U( 500 )

ENTER rational A/B  A,B = ? 135795,345660
 135795 / 345660  =  12345 * U( 500 )
L'idée maitresse est de construire l'indice i depuis les bits de poids faible vers ceux de poids forts à l'aide de p donnant les puissances croissantes de 2 ( 1 → 2→ 4 → ... ). dans i, les seuls bits mis à 1 sont ceux correspondant à a>b et le bit final de plus haut poids qui est atteint lorsque a=b. La mise à 1 du bit se fait par l'addition i+p. A chaque pas, comme le fait jxano les numérateurs et dénominateur sont soustraits selon que a<b ou a>b (Algorithme d'Euclide).
L'arrêt se fait pour a=b. Mais on aura a>1 lorsque l'utilisateur n'a pas entré une fraction irréductible à la fin de l'algorithme d'Euclide, a (ou b) contient le PGDC. Dans le cas contraire, a et b sont premiers entre eux et le critère d'arrêt a=b s'obtient pour a=1 et b=1.

Evidemment, ce code peut être MPOïsé, voici une version plus compacte pour SHARP PC-1360:

Code : Tout sélectionner

1:I=0,P=.5: INPUT A,B
2:P=2*P: IF A<B LET B=B-A: GOTO 2
3:I=I+P: IF A>B LET A=A-B: GOTO 2
4:PRINT A,"U"+ STR$ I 
PC-1360 1x 53 162 U7340024.png
PC-1360 1x 53 162 U7340024.png (49.88 Kio) Vu 6255 fois
PC-1360 123x 53 162 U7340024.png
PC-1360 123x 53 162 U7340024.png (50.77 Kio) Vu 6255 fois
jxano a écrit : 01 sept. 2020 19:41 [...]J'ai rêvassé un peu longtemps sur la représentation en H des 7 premiers niveaux de l'arbre de Calkin-Wilf en me demandant s'il y avait une façon pratique de numéroter les sommets.[...]
Je rêvassais moi aussi sur cette représentation en H de l'arbre de Calkin Wilf, mais en me demandant comment trouver une relation simple entre les coordonnées cartésiennes (x,y) d'un rationnel U(i)=a_i/b_i sur la figure et son indice i dans l'arbre ! Rien de concret ou satisfaisant n'a, pour le moment, émergé de mes rêveries et hallucinations.
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 »

J'ai trouvé l'idée de l'indice calculé à partir du rationnel en lisant la page Wikipedia consacrée à l'arbre de Calkin-Wilf. On y dit que la structure est bien un arbre parce qu'on peut accéder à tout noeud depuis n'importe quel autre, y compris la racine, ce qui implique qu'on peut "descendre" (par addition) et "monter" (par soustraction). Comme je savais "indicer" les noeuds dans un sens, l'autre sens est venu tout seul.

Et quand la fraction est réductible ? Je me suis assez vite aperçu que la clause d'arrêt (la racine est atteinte) est mal formulée. Plutôt que de dire : numérateur et dénominateur sont tous deux égaux à 1, pourquoi ne pas dire : les deux sont égaux entre eux ? J'ai modifié le test dans mon dernier programme et ça marche. En fait, l'algorithme de remontée fait la réduction du même coup. Il suffit de donner la fraction réduite avec l'indice résultat en divisant les N et D de départ par le N obtenu. On entre deux entiers positifs et la machine se débrouille.

10 PRINT "INDICE DANS ARBRE C-W": CLEAR
12 DIM A(30)
20 INPUT "NUMER",N,"DENOM",D:I=0:A=N:B=D
30 IF N=D;R=1: GOTO 40
32 IF N>D;A(I)=1:N=N-D: GOTO 34
33 D=D-N:A(I)=0
34 I=I+1: GOTO 30
40 I=I-1: IF I<0; GOTO 50
42 R=2*R+A(I): GOTO 40
50 PRINT "IND(";A/N;"/";B/N;")=";R: GOTO 20

(C.Ret, tu as eu la même idée que moi dans ton code apparu lors de la rédaction du présent message. Des choses m'ont échappé dans ton message réédité d'hier.)

J'ai quelques idées de représentation en H de l'arbre sur écran avec ou sans interface de navigation, mais tant que rien n'est fait...
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 »

Oui, ton idée était la bonne, le critère de fin est bel et bien a=b et non pas ( a=1 AND b=1 ) qui n'est réalisé que dans le cas d'une fraction irréductible, c'est à dire lorsque a et b sont premiers entre eux.

Dans un premier temps, j'avais eut l'idée de faire une première partie qui réduit la fraction. je ne savais plus exactement comment initier l'algorithme de calcul du PGDC(a,b). En me documentant j'ai remarqué quelque chose d'important:

Quand on regarde l'algorithme, on se rend compte que l'on retire toujours le plus petit au plus grand. C'est bien se que l'on fait lors du calcul de l'indice pour remonter vers le rationnel père.

Il y a donc une très forte similitude entre l'algorithme de détermination de l'indice i de U(i)=A/B et l'algorithme d'Euclide pour le calcul du PGDC(a,b).

J'ai donc entrepris de mélanger les deux partie, c'est à dire de déterminer simultanément le PGCD(a,b) et l'indice i de U(i)=a/b.
A ma grande surprise, il n'y apas besoin de mixer quoi que ce soit, ton algorithme de calcul de l'indice extrait très naturellement etsans aucun code supplémentaire le PGDC qui est en fait tout simplement la valeur de a (ou b) lorsque l'on atteint le critère de fin a=b.

Voici, mis cote à cote, le déroulement de la détermination pour a/b=11/28 et a/b=33/84 :

Code : Tout sélectionner

A  /  B       p   Test      Décompo bin    i          A  /  B       p   Test      Décompo bin    i
11 / 28       1   11 < 28   %        0b    0          33 / 84       1   33 < 86   %         0b   0
11 / 17       2   11 < 17   %       00b    0          33 / 51       2   33 < 51   %        00b   0
11 /  6       4   11 >  6   %      100b    4          33 / 18       4   33 > 18   %       100b   4
5  /  6       8    5 <  6   %     0100b    4          15 / 18       8   15 < 18   %      0100b   4
5  /  1      16    5 >  1   %    10100b   20          15 /  3      16   15 >  3   %     10100b  20
4  /  1      32    4 >  1   %   110100b   52          12 /  3      32   12 >  3   %    110100b  52
3  /  1      64    3 >  1   %  1110100b  116           9 /  3      64    9 >  3   %   1110100b 116
2  /  1     128    2 >  1   % 11110100b  244           6 /  3     128    6 >  3   %  11110100b 244
1  /  1     256    1 =  1   %111110100b  500           3 /  3     256    3 =  3   % 111110100b 500
     ==>  11  /  28  =  1  . U ( 500 )                     ==>  33  /  84  =  3  . U ( 500 )      
On voit qu'exactement la même séquence est utilisée pour les deux calculs. Que tout est identique, mis à part le facteur 3 entre les numérateur et dénominateurs des deux fractions. Et ce facteur 3 persiste jusqu'à la fin de l'algorithme.

D'où les codes simplissimes que nous obtenons:

Code : Tout sélectionner

10 PRINT "INDICE DANS ARBRE C-W": CLEAR
12 DIM A(30)
20 INPUT "NUMER",N,"DENOM",D:I=0:A=N:B=D
30 IF N=D;R=1: GOTO 40
32 IF N>D;A(I)=1:N=N-D: GOTO 34
33 D=D-N:A(I)=0
34 I=I+1: GOTO 30
40 I=I-1: IF I<0; GOTO 50
42 R=2*R+A(I): GOTO 40
50 PRINT "IND(";A/N;"/";B/N;")=";R: GOTO 20

Code : Tout sélectionner

1:I=0,P=.5: INPUT A,B : N=A,D=B
2:P=2*P: IF A<B LET B=B-A: GOTO 2
3:I=I+P: IF A>B LET A=A-B: GOTO 2
4:PRINT STR$ N;"/"; STR$ D;"=" STR$ (N/A);"/"; STR$ (D/A);"= U"+ STR$ I 
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 »

Le code simplissime a deux grandes qualités : on n'attend pas longtemps le résultat et on peut l'insérer comme fonction dans un programme plus étoffé, comme par exemple le parcours en largeur de l'arborescence de Stern-Brocot, pour calculer l'indice de chaque fraction créée. Je suis en train de regarder ce que ça donne.

Une petite chose que j'ai du mal à intégrer est qu'on ait pas besoin a priori de connaître la longueur de l'indice en binaire avant de le calculer. Je cherchais dans mes algorithmes à former les coefficients 0 ou 1 d'un polynôme à passer ensuite dans un schéma de Horner. Ta méthode par la somme des puissances inverse le processus, ce qui fait qu'on attaque le calcul de l'indice par les premières puissances de 2, donc un aller simple suffit.
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 »

L'attaque peut se faire dans les deux sens, c'est parfaitement symétrique.
Pour déterminer l'indice à partir du rationnel A/B, on peut balayer les puissances de deux crescendo, c'est à dire: 2^0 → 2^1 → ... → 2^p
Pour déterminer le rationnel A/B à partir de son indice, on balayer les puissance dans l'autre sens, c'est à dire en ordre décroissant: 2^p > 2^(p-1) > ... > 2^1 > 2^0
Et dans els deux cas, p = INT( LOG2(n) )

Voici, cote à cote les deux algorithmes afin de montrer la symètrie:

Code : Tout sélectionner

Quel est l'indice i du rationnel A/B ?                Quel est l'irréductible A/B d'indice i ?
A  /  B       p   Test      Décompo bin    i             i  Décompo bin      p   Test       A  /  B
11 / 28       1   11 < 28   %        0b    0           500  %111110100b    256   500≥256    1  /  1
11 / 17       2   11 < 17   %       00b    0           244  % 11110100b    128   244≥128    2  /  1
11 /  6       4   11 > 6    %      100b    4           116  %  1110100b     64   116≥ 64    3  /  1
5  /  6       8    5 < 6    %     0100b    4            52  %   110100b     32    52≥ 32    4  /  1
5  /  1      16    5 > 1    %    10100b   20            20  %    10100b     16    20≥ 16    5  /  1
4  /  1      32    4 > 1    %   110100b   52             4  %     0100b      8     4<  8    5  /  6
3  /  1      64    3 > 1    %  1110100b  116             4  %      100b      4     4≥  4   11  /  6
2  /  1     128    2 > 1    % 11110100b  244             0  %       00b      2     0<  2   11  /  17
1  /  1     256    1 = 1    %111110100b  500             0  %        0b      1     0<  1   11  /  28
    ==>  11  /  28  =  x1   U ( 500 )                     ==>  U( 500 ) =  11 / 28   
La symétrie provient du fait que la décomposition binaire de l'indice donne sa position dans l'arbre de Calkin Wilf et son code génétique, c'est à dire la façon dont il est construit.
Pour calculer l'indice, on remonte l'arbre depuis A/B jusqu'à la racine et donc on parcourt le code génétique de bas en haut. (bit de poids faible vers les forts). Lorsque a<b, on remonte par une branche à gauche (bit=0 , B=b-a) et si a>b on remonte par une branche à droite (bit=1 , A=a-b). Le critère d'arrêt a=b est atteint quand on est remonté jusqu'à la racine de l'arbre (qui vaut 1 ou le PGDC(A,B) si la fraction n'était pas irréductible).

Pour calculer le rationnel A/B à partir de son indice, on descend l'arbre en parcourant les bits de l'indice de haut en bas. Le bit le plus haut est toujours à 1, il s'agit de l'indice de la racine. Les suivant indiquent de quel coté (par quelle branche) on descend l'arbre. Les bits pairs pointent vers les rationnels inférieurs à l'unité (c'est à dire A<B , bit=0, i<p, B=a+b), les bits impairs pointent vers les rationnels supérieurs à l'unité (c'est à dire A>B, bit=1, i≥p , A=a+b ). On arrête notre descente au bit de parité de l'indice. Contrairement à la méthode utilisant les fractions continues, il n'y a pas d'inversion à réaliser.



Et le code incluant les deux calculs peut ressemble à ceci:

Code : Tout sélectionner

10:"A" INPUT "A/B ",A,B                 20:"N" INPUT "U";I                     
11:I=0,P=.5                             21:A=0,B=1,P=2*2^ INT ( LOG I/ LOG 2)
12:P=2*P:IF A<B LET B=B-A: GOTO 12      22:P=P/2:IF I< INT P LET B=A+B: GOTO 22
13:I=I+P:IF A>B LET A=A-B: GOTO 12      23:IF I>=P LET A=A+B,I=I-P:GOTO 22  
14:PRINT A,"U"+ STR$ I: GOTO 21         24:PRINT STR$ A;"/";B: GOTO 11
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 : 29 août 2020 13:53 Je suis en train de préparer la version pour HP-65 :)

Image
Re !

J'ai donné à manger ton code à ma HP-65 :P
J'avoue que j'ai pas pris le temps de piger comment ça fonctionne, en ce moment avec la reprise et la rentrée des gamins c'est chaud... mais j'aime bien l'utilisation des LBL A et LBL B pour revoir le numérateur et le dénominateur rapidement, c'est nickel au niveau UX (comme on dit maintenant :D).
Et c'est effectivement super rapide : 18 secondes pour U(500), 24 secondes pour U(5000) 8)

Par contre bizarrement, autant pour U(500) j'obtiens bien 11/28, pour les autres que j'ai testés je n'ai pas les mêmes valeurs qu'avec les autres algos :|
Par exemple ça me donne :
U(10) = 4/3 (au lieu de 3/5)
U(50) = 9/7 (au lieu de 7/12)
U(5000) = 109/33 (au lieu de 43/162)

Ouate de phoque 8O :?: :D
? 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 [...]
Par contre bizarrement, autant pour U(500) j'obtiens bien 11/28, pour les autres que j'ai testés je n'ai pas les mêmes valeurs qu'avec les autres algos :|
Par exemple ça me donne :
U(10) = 4/3 (au lieu de 3/5)
U(50) = 9/7 (au lieu de 7/12)
U(5000) = 109/33 (au lieu de 43/162)

Ouate de phoque 8O :?: :D
Zut, doit y avoir une pouille de la notage. Je reprends ma copie sur HP-15C et vérifie cela.

EDIT:
je n'ai pas ces erreurs sur l'HP-15C !
C'est peut-être une erreur entre les deux version, j'ai peut-être mal interpréter ce que fait faire une séquence à cette pauvre HP-65. Par contre, si c'est cela pourquoi U(500) est juste ???

U(10) renvoie U(9), U(50) renvoie U(49) j'entrevois où chercher, mais U(5000) renvoie U(2503) ? Bizarre ?? 5000 D ne donne pas 139 R/S 43 ???

Après avoir calculer U(10) (et renvoyer un résultat faux), que contiennent les registres R1:R2:R3:R4 et R5: ? Il n'y a pas d'erreur ?
Normalement, il n'y a pas besoin d'appuyer sur A ou B, on lance par 10 D et 3.000 s'affiche, on presse sur R/S et 5.000 s'affiche, on en déduit que U(10)=3/5. C'est comme cela que ça se passe ?

(Attention vers la fin du code, les instructions 043 à 046 sont RCL3 RCL4 + x>y? GTO0, est-ce correctement saisi dans la machine ?)


De toute façon, suite aux très intéressants et instructifs échanges avec jxano, cette version utilisant les fractions continues est maintenant obsolète. En effet, il existe une façon de faire plus courte et plus rapide (sur le papier) et j'espère qu'elle donnera les bons résultats avec l'HP-65 de Danny):
MPO 95 - HP-65 Calkin Wilf suite U_n using binary decomposition and JXANO algorithm.gif
MPO 95 - HP-65 Calkin Wilf suite U_n using binary decomposition and JXANO algorithm.gif (26.48 Kio) Vu 6190 fois
Usage:
Saisissez l'indice, pressez la touche [ D ], le numérateur A s'affiche, pressez [R/S] pour afficher le dénominateur B, pressez alors sur [ ÷ ] pour obtenir une valeur approchée du rationnel.
Les touches [ A ] et [ B ] peuvent être utilisées pour afficher à nouveau respectivement le numérateur A et le dénominateur B.
Alternativement, [RCL][ 1 ] et [RCL][ 2 ] ont le même effet car A et B sont mémorisés respectivement dans les registres R1 et R2.
L'indice doit être supérieur ou égal à 1.
Modifié en dernier par C.Ret le 05 déc. 2021 10:19, 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.
Répondre

Retourner vers « Tous les Pockets »