Dans un premier temps, en lisant un peu vite ce dernier code, je me suis demandé pourquoi il y avait des NOP !
Et puis j'ai réalisé en lisant les explications que comme il n'y avait ni label, ni moyen d'éditer le code saisi, il fallait bien évidemment prévoir l'adresse des sauts.
Et alors, je me suis rendu compte que j'étais bien mauvais à cet excercice (à force d'utiliser des machines sophistiquées, on ne se rend plus compte que pour programmer de véritables HP classics, il faut être malin et avoir prévu à l'avance l'adresse où s'exécutera les diffèrentes parties du programme.
Pour y voir plus clair, j'ai recopié ce programme et j'y ai porté le contenu des registres pour faire apparaitre la logique de fonctionnement qui ne m'était pas apparue évidente au premier abord.
Je poste ci-dessous le programe de
Marge mis en forme.
Les adresses suivies d'un * indiquent le lieu des branchements, cela permet de mettre en évidence les sauts et la boucle principale.
Le contenu de la pile est annoté afin de faire apparaitre le principe de calcul qui reprend les variables comme dans mes listings :
n pour désigner le
n-ième terme de la suite (puis
n' et
n" en fonction de l'évolution de
n à chaque "tour" de la boucle principale)
a et
b car il s'agit bien en fait du principe de calcul : a' <- b et b' <- a+b
Code : Tout sélectionner
Program Code Mnemonic Stack: Registres:
t: z: y: x: L: R0:
n
01 15 71 x=0?
02 RTN 0 \\ Renvoi F(0)=0
03 2 2 n 2
04 21 x<->y 2 n
05 14 41 x<=y? \\ Test n<=2 ?
06 13 25 GTO 25 \\ Pas de label, saut direct
07 3 3 2 n 3
08 41 - 2 n-3 3
09 23 0 STO 0 n-3
10 1 1 2 n-3 1
11 31 ENTER 2 n-3 1 1
~ a b \\ avec n'=n-3, a=1 et b=1 initialement
12* 51 + ~ ~ n' a+b b n'
13 14 73 LAST x 2 n' a+b b
14 21 x<->y 2 n' b a+b
15 24 0 RCL 0 n' b a+b n'
16 15 71 x=0? \\ Test n'=0 (fin de boucle)
17 13 30 GTO 30
18 1 1 b a+b n' 1
19 41 - ~ b a+b n"
20 23 0 STO 0 n" \\ Decremente n"=n'-1 pour boucle suivante
21 22 Rd ~ ~ b a+b
22 13 12 GTO 12
23 15 13 NOP
24 15 13 NOP
25* 1 1 2 1 \\ Renvoi F(1)= 1
26 74 R/S
27 15 13 NOP
28 15 13 NOP
29 15 13 NOP
30* 22 Rd 0 0 b a+b \\ Renvoi F(n)=a+b
31 74 R/S
Je dois avouer que je ne suis pas fort et très maladroit avec ce style de programmation (sans label).
Mais, à partir de l'excellent modèle fourni par
Marge, et en composant sur papier (incapable de composer directement ce type d'optimisation sur la machine, il me faut une vision précise des mouvements de la pile et des sauts !!).
Je suis tout de même capable de proposer une version optimisée (17 pas de programme et pas d'utilisation du registre mémoire R0).
Code : Tout sélectionner
Program Code Mnemonic Stack:
t: z: y: x: L:
n
01 1 1 n 1
02 21 x<->y 1 n \\ initialise le calcul avec a= 1 et b = 0
03 0 0 1 n 0 \\ en plaçant les trois valeurs (a b et n)
04 21 x<->y 1 0 n \\ dans l'ordre attendu pour boucle principale
05* 15 71 x=0? ~ a b n \\ ********* Boucle principale
06 13 17 GTO 17 \\ Test n=0 (fin de boucle principale)
07 1 1 a b n 1
08 41 - a a b n-1 1 \\ dec n
09 22 Rd n-1 a a b
10 51 + n-1 n-1 a a+b b \\ b' <- a+b
11 14 73 LAST x n-1 a a+b b \\ a' <- b
12 21 x<->y n-1 a b a+b
13 22 Rd a+b n-1 a b \\ 3 x Rd vaut 1 x Rup
14 22 Rd b a+b n-1 a
15 22 Rd a b a+b n-1
16 13 5 GTO 05 ~ a' b' n' \\ Boucle principale (a'=b b'=a+b n'=n-1)
~ ~ b n \\ Pas de Nop car écrit au propre sur papier avant saisie :-)
17* 22 Rd n ~ ~ b \\ Renvoi F(n)= b
18 74 RTN \\ Fin du programme optimisé
Et son équivalent pour RPL :
Code : Tout sélectionner
« 0 1 ROT // Initialise calcul avec b=0 a=1 et n
// place dans la pile 3:b 2:a 1:n (initialement b=0 a=1 et n=n)
WHILE DUP // tant que n>0
REPEAT
1 - // decrémente: n'=n-1
ROT ROT OVER + // calcule : b'=a+b et a'=b
SWAP ROT // replace dans l'odre 3:b' 2:a' 1:n'
END
DROP2 // supprime a' et n' et renvoi F(n) = b'
»