[HP-41C] Profitons-en, "PGCDons" !

[Thierry Loiseau]

Depuis mon précédent programme, voilà une application bien pratique...

[Thierry Loiseau]

J'ai tenté de me creuser la tête en n'utilisant que la pile opérationnelle...

Code : Tout sélectionner

01 LBL "PGCDST"
02 CF 29
03 FIX 0
04 CLA
05 AVIEW
06"NUMERATEUR : "
07 PROMPT			
08"DENOMINATEUR : "
09 PROMPT
10 CLA
11 AVIEW
12 LBL 00				
13 STO Z
14 MOD	
15 ENTER
16 1
17 X<>Y	
18 X<=Y?
19 GTO 02
20 X<>Y
21 RDN
22 GTO 00
23 LBL 02
24 X=0?
25 RCL Z
26"PGCD="
27 ARCL X
28 AVIEW
29 END

Ça marche mais je ne suis pas certain de ma logique RPNienne

[Marge]

Ton message initial est une jolie présentation en tout cas.

[Ben]

Un programme que j'avais fait, il y a quelques mois pour calculer les PGCD et PPCM. Il utilise quelques mémoires.

La méthode pour le calcul est le même que celle apprise à l'école. Soustraction de A et B. Ensuite, on soustrait le résultat avec le plus petit des 2 termes de la soustraction. On répète jusqu'à ce que le résultat=0. Le PGCD est le dernier résutat non nulle.
PPCM = (A*B)/E

Code : Tout sélectionner

01 LBL PGCD
02 STO 01
03 X<>Y
04 STO 02
05 LBL 01
06 X>Y?
07 X<>Y
08 STO 03
09 -
10 X=0?
11 GTO 02
12 RCL 03
13 GTO 01
14 LBL 02
15 LASTX
16 STO 03
17 PGCD=
18 ARCL x
19 AVIEW
20 PSE
20 RCL 01
21 RCL 02
22 *
23 RCL 03
24 /
25 PPCM=
26 ARCL X
27 AVIEW
29 END

Ben

[Thierry Loiseau]

Merci pour ta version

[Ben]

Il y a sûrement moyen de l'optimiser.

J'ai voulu respecter la méthode de calcul qu'on apprend à l'école

[C.Ret]

C'est bien de respecter la méthode apprise à l'école.

On peut aussi utiliser la congruence. l'algorithme reste le même mais l'on remplace la soustraction par le calcul du reste de la division euclidienne. cela va donc converger bien plus vite vers le PGDC.

Comme pour le programme de ben, ce code calcule le PGDC (GCD en anglais) et le PPMC de deux entiers a et b:

Code : Tout sélectionner

PC PRoGRaMme               Contenu de la pile:                       Commentaires:
                           t:         z:         y:         x:
01 LBL "GCD                 .          .          a          b          
02 RCL Y                    .          a          b          a       // Copie de a et b dans la pile opérationelle
03 RCL Y                    a          b          a          b 
04 LBL 00                                                            // Boucle de l'algorithme d'euclide (PGDC) 
05 MOD                        
06 LastX                    a          b          r          b     
07 x<>y  x#0?  GTO 00                                                // Boucle jsuqu'à reste r=0, b est alors le PGDC
10 +                                   a          b    gcd(a,b)      // Astuce pour faire disparaitre le terme null
11 ST/ T                a/gcd          a          b         gcd 
12 /                               a/gcd          a       b/gcd      // Calcul a'/b'  fraction irréductible a/b  
13 ST* Y                           a/gcd    a.b/gcd       b/gcd      // Calcul le PPMC   =  a*b/gcd(a,b)      	
14 x<>y                            a/gcd      b/gcd     a.b/gcd      // Met en place dans la pile
15 Lastx                a/gcd      b/gcd    a.b/gcd         gcd      // 
16 END

Code : Tout sélectionner

01 LBL "GCD                           // Les arguments a et b sont dans la pile
     RCL Y  RCL Y                     // Copie a et b
04 LBL 00                             // Boucle de l'algorithme d'euclide (PGDC) 
     MOD  LastX  x<>y  x#0?  GTO 00   // Boucle jsuqu'à reste nul, b est alors le PGDC
10 +  ST/ T  /  ST* Y  x<>y  Lastx    // Met en place dans la pile frraction irréductible a/b, PPMC, PGDC
16 END 

Code : Tout sélectionner

Utilisation :
Les termes a et b sont en y et x dans la pile de la calculette.

Exemple :
 950796 [ENTER^] 107016 [XEQ][Alpha]GCD[Alpha]  affiche 4116     = PGDC( 950796 , 107016 ) le plus grand diviseur commun
 Une pression sur                       [ R↓ ]  affiche 24720696 = PPMC( 950796 , 107016 ) le plus petit multiple commun
                                        [ R↓ ]  affiche 26       = b'                   
                                        [ R↓ ]  affiche 231      = a'  La fraction 950796/107016 se réduit donc à 231/26
                                        [ R↓ ]  revient à l'affichage du PGDC , etc.

(d'après programme trouvé sur le site du MoHP muséum et Yolasite)

[Thierry Loiseau]

Grand merci pour ce code commenté !

Code : Tout sélectionner

02 RCL Y                    .          a          b          a       // Effectue une copie de a et b dans la pile opérationelle
03 RCL Y                    a          b          a          b

Astucieux

[C.Ret]

C'est l'origine de l'instruction DUP2 que l'on trouvera par la suite sur les calculatrices R.P.L.
Comme beaucoup de fonctions et instructions sont diadiques (prennent deux arguments), copier les deux arguments une seule instruction devient fort utile.

[Thierry Loiseau]

C'est bien de respecter la méthode apprise à l'école.

On peut aussi utiliser la congruence. l'algorithme reste le même mais l'on remplace la soustraction par le calcul du reste de la division euclidienne. cela va donc converger bien plus vite vers le PGDC.

Comme pour le programme de ben, ce code calcule le PGDC (GCD en anglais) et le PPMC de deux entiers a et b:

PGCD ? ou PPCM ?
PGDC ? ou PPMC ?

PGCD... et PPCM !
Pleins de souvenirs pour moi

[C.Ret]

Je crois que les acronymes corrects sont PGCD et PPCM en français.

Les PGDC et PPMC sont en fait une erreur de ma part, je pratique trop le franglais et autres "plates" germaniques et "spam" anglé-tiqué, ( c'est comme polymère et polynôme...

Je suis un peu dyslexique, surtout lorsque je prépare mes posts à partir de documents en langue étranges.

[Thierry Loiseau]

Oui, je vérifie et...

[Thierry Loiseau]

Je crois que les acronymes corrects sont PGCD et PPCM en français.

Les PGDC et PPMC sont en fait une erreur de ma part, je pratique trop le franglais et autres "plates" germaniques et "spam" anglé-tiqué, ( c'est comme polymère et polynôme...

Je suis un peu dyslexique, surtout lorsque je prépare mes posts à partir de documents en langue étranges.

Vous êtes tout excusé maître C.Ret ...

mais acronyme ou sigle, that is the question...

[C.Ret]

Comme pour le programme de ben, ce code calcule le PGDC (GCD en anglais) et le PPMC de deux entiers a et b:(d'après programme trouvé sur le site du MoHP muséum et Yolasite)

Je viens d'en apprendre un peu plus sur ce code pour HP-41C: l'auteur en personne nous donne ici quelque détail l'origine de cette merveille de simplicité et efficacité.

[Danny]

C'est le MPO ultime