Misez p'tit, Optimisez - N°16 (Fibonacci)

[Hobiecat]

L'exemple de C.Ret sur le fil 39GII m'a rappelé que nous n'avons pas fait de MPO depuis longtemps !

L'objectif de ce MPO : avec comme donnée d'entrée le rang n, calculer le nombre de Fibonacci de rang n, F(n)

Points particuliers :
- le programme devra traiter les cas particuliers F(0)=0 et F(1)=1
- vous calculez avec la méthode qui vous convient : soit en récursif, soit avec le calcul direct (voir la page wikipedia pour ceux qui ont des trous de mémoire)

Comme d'habitude, l'économie de pas de programme est la règle !

[pir2]

Tiens, marrant, je me suis fait çà sur ma 15C pour voir si je n'étais pas trop rouillé
(pas optimisé par contre)

Allez, çà va me faire un exercice de lecture des codes programmes de la 15C LE

Code : Tout sélectionner

001 - 42.21.11 LBL A
002 - 1        1
003 - 43.30. 9 TEST 9 (x>=y?)
004 - 22 1     GTO 1
005 - 30       -
006 - 44 0     STO 0
007 - 1        1
008 - 36       ENTER
009 - 42.21. 0 LBL 0
010 - 40       +
011 - 43 36    LSTx
012 - 34       x<>y
013 - 42. 5. 0 DSE 0
014 - 22 0     GTO 0
015 - 42.21. 1 LBL 1

Edith me dit que c'est draft, pas tout à fait juste, mais c'est un début (pas de traitement de f(0) et f(1), pas sûr que f(2) soit juste etc..)
Edith2 m'a nettoyé tout çà

[pir2]

Et le même (ou presque) pour HP-41

Code : Tout sélectionner

01 LBL^FIBO
02 1
03 X>Y?
04 GTO 01
05 -
06 X=0?
07 GTO 02
08 1
09 ENTER^
10 LBL 00
11 +
12 LASTX
13 X<>Y
14 DSE Z
15 GTO 00
16 LBL 02
17 1
18 LBL 01

Pas de X>=Y? sur 41 (4 pas de perdus)

[zpalm]

Un peu plus court sur 15C:

Code : Tout sélectionner

001 - 42,22,11 LBL A
002 - 43 20    x=0?
003 - 43 32    RTN
004 - 44 0     STO 0
005 - 1        1
006 - 36       ENTER
007 - 0        0
008 - 42.21. 0 LBL 0
009 - 40       +
010 - 43 36    LSTx
011 - 34       x<>y
012 - 42. 5. 0 DSE 0
013 - 22 0     GTO 0

Et l'équivalent sur 41C et 42s en n'utilisant que la pile:

Code : Tout sélectionner

HP-41C            HP-42S
                  00 { 22-Byte Prgm}
01  LBL 'FIB#     01  LBL"FIB#"
02  X=0?          02  X=0?             * cas particulier F(0) => on retourne 0
03  RTN           03  RTN
04  1             04  1                * x:1, y:N
05  0             05  0                * x:0, y:1, z:N qui va servir de compteur de boucles
06  LBL 00        06  LBL 00           
07  +             07  +                * calcul F(n+1)=F(n)+F(n-1)
08  LASTX         08  LASTX            * on rappelle F(n)
09  X<>Y          09  X<>Y             * x: F(n+1), y: F(n), z:compteur de boucle
10  DSE Z         10  DSE ST Z         * on décrémente z et on teste si on est arrivé à 0
11  GTO 00        11  GTO 00           
12  END           12  END              * après N boucles on sort

Sur WP 34S, trop facile:

Code : Tout sélectionner

FIB

[Hobiecat]

Tiens, marrant, je me suis fait çà sur ma 15C pour voir si je n'étais pas trop rouillé
(pas optimisé par contre)

Allez, çà va me faire un exercice de lecture des codes programmes de la 15C LE

Edith me dit que c'est draft, pas tout à fait juste, mais c'est un début (pas de traitement de f(0) et f(1), pas sûr que f(2) soit juste etc..)
Edith2 m'a nettoyé tout çà

Bien, mais y'a un petit bug : F(4) donne 5 alors que normalement c'est F(5) qui donne 5. Un petit décalage quoi !

[Hobiecat]

Un peu plus court sur 15C:

Il ne marche pas celui-ci : F(5) donne 34 ??

Petit rappel pour les tests :
F(0)=0
F(1)=1
F(2)=1
F(3)=2
F(4)=3
F(5)=5
F(6)=8
F(7)=13
F(8)=21
F(9)=34

Sur WP 34S, trop facile:

Code : Tout sélectionner

FIB

Je n'ai pas trouvé la fonction ! Dommage qu'on ne puisse pas faire XEQ "FIB" d'ailleurs sur la 34S...(ou alors je n'ai pas trouvé, la seule solution que j'ai trouvée est h/x.fcn puis de faire défiler)

[pir2]

0 1
1 1
2 2
3 3
4 5
5 8

Je suis parti de F(0)=F(1)=1

[pir2]

Voilà, c'est fait

Code : Tout sélectionner

001 - 42.21.11 LBL A
002 - 43.20    x=0
003 - 31       R/S
004 - 1        1
005 - 43.30. 5 TEST 5 (x=y)
006 - 31       R/S
007 - 30       -
008 - 44 0     STO 0
009 - 0        0
010 - 36       ENTER
009 - 1        1
011 - 42.21. 0 LBL 0
012 - 40       +
013 - 43 36    LSTx
014 - 34       x<>y
015 - 42. 5. 0 DSE 0
016 - 22 0     GTO 0

[zpalm]

Un peu plus court sur 15C:

Il ne marche pas celui-ci : F(5) donne 34 ??

Petit rappel pour les tests :
F(0)=0
F(1)=1
F(2)=1
F(3)=2
F(4)=3
F(5)=5
F(6)=8
F(7)=13
F(8)=21
F(9)=34

C'est exactement ce que j’obtiens sur ma 15C LE. Il faut peut être ajouter un "R/S" à la fin pour ne pas exécuter du code qui traînerai en mémoire...

Une version améliorée pour la 42s:

Code : Tout sélectionner

00 { 20-Byte Prgm}
01  LBL"FIB#"
02  X=0?             * cas particulier F(0) => on retourne 0
03  RTN
04  1                * X:1, Y:n
05  LOG              * L:1  X:0, Y:n qui va servir de compteur de boucles
06  LBL 00           * L:F(n-1) X:F(n) Y:n
07  RCL+ ST L        * calcul F(n+1)=F(n)+F(n-1) => L:F(n) X:F(n+1) Y:n
08  DSE ST Y         * on décrémente Y et on teste si on est arrivé à 0
09  GTO 00           
10  END              * après N boucles on sort

[pir2]

Et pour 41

Code : Tout sélectionner

01 LBL^FIBO
02 X=0?
03 STOP
04 1
05 X=Y?
06 STOP
07 -
08 0
09 1
10 LBL 00
11 +
12 LASTX
13 X<>Y
14 DSE Z
15 GTO 00

[zpalm]

(ou alors je n'ai pas trouvé, la seule solution que j'ai trouvée est h/x.fcn puis de faire défiler)

Sur la WP 34S Il faut effectivement passer par le catalogue x.fcn, mais pour se positionner dans le catalogue tu peux taper les lettres de la fonction, par h x.fcn F te positionne sur la première fonction commençant par F

[Hobiecat]

C'est exactement ce que j’obtiens sur ma 15C LE. Il faut peut être ajouter un "R/S" à la fin pour ne pas exécuter du code qui traînerai en mémoire...

Oups, effectivement, j'avais oublié le "Clear PRGM" avant d'entrer ta version sur 15C....

Sur la WP 34S Il faut effectivement passer par le catalogue x.fcn, mais pour se positionner dans le catalogue tu peux taper les lettres de la fonction, par h x.fcn F te positionne sur la première fonction commençant par F

C'est mieux, mais pas idéal quand même...quand on veut atteindre les fonctions commençant par des lettres grecques ou des symboles, il faut tout faire défiler (certes, on peut faire défiler "à l'envers" pour être tout de suite à la fin). L'avantage quand même est que la machine garde en mémoire la dernière fonction.

[C.Ret]

Wouah ! Ce Misez P'tit démarre très fort.

Je peine à trouver mieux que les codes déjà listés ci-dessus.

Donc, je vais proposer quelque chose pour HP28S, ce qui sera pour un temps seulement le mieux puisque rien n'a encore été posté ici pour cette machine :

Code : Tout sélectionner

'F(n)=IFTE( n<2 , n , F(n-1)+F(n-2) )' DEF

Bon d'accord, ce n'est pas très original. Mais cela fonctionne (mal car très long et très gourmant en mémoire à cause du nombre incroyable de calculs qu'engendre les appels récursifs !).

En tout cas c'est plus lisible que le code suivant, qui lui par contre est efficace :

Code : Tout sélectionner

« 0 OVER SIGN 2 4 ROLL START DUP2 + NEXT » 'FIB' STO

Comme vous ne l'avais certainement pas remarqué (car le RPL c'est assez illisible), ce code rempli la pile avec les termes successifs de la série de Fibonacci jusqu'à celui spécifié. Le résultat est donc celui au niveau 1: à la fin de son execution.

Bon allez, j'ai pitié, je poste la version structurée et commentée.

Code : Tout sélectionner

« "Calcul des termes de la suite de Fibonacci" DROP
  -> n
   « "Initialise la suite avec F0=0 et F1=1" DROP
     0 n SIGN    
        "^--- une astuce pour le cas où n=0, la somme fera quoi qu'il arrive toujours 0" DROP

     "Boucle principale de 2 à n (si n=0 ou n=1 on fait une fois la boucle" DROP
     "Par chance le résultat avec n=1 est alors valide. Et celui avec n=0 " DROP
     "est garanti par la fonction SIGN" DROP
 
     2 n START
         DUP2 +  "Additionne les deux derniers termes tout en en laissant une copie dans la pile" DROP
     NEXT
     "Fin du programme        " DROP  "C'est chouette ces commentaires en RPL ! Non ?" DROP
   »
»
'FIB' ST'FIB' ST

[badaze]

Wouah ! Ce Misez P'tit démarre très fort.

Je peine à trouver mieux que les codes déjà listé ci-dessus.

Donc, je vais proposer quelque chose pour HP28S, ce qui sera pour un temps seulement le mieux puisque rien n'a encore été posté ici pour cette machine :

Code : Tout sélectionner

'F(n)=IFTE( n<2 , n , F(n-1)+F(n-2) )' DEF

Bon d'accord, ce n'est pas très original. Mais cela fonctionne (mal car très long et très gourmant en mémoire à cause du nombre incroyable de calculs qu'engendre les appels récursifs !).

En tout cas c'est plus lisible que le code suivant, qui lui par contre est efficace :

Code : Tout sélectionner

« 0 OVER SIGN 2 4 ROLL START DUP2 + NEXT » 'FIB' STO

Comme vous ne l'avais certainemetn pas remarqué (car le RPL c'est assez illisible), ce code rempli la pile avec les termes successifs de la série de Fibonacci jusqu'à celui spécifié. Le résultat est donc celui au niveau 1: à la fin de son execution.

Bon allez, j'ai pitié, je poste la version structurée et commentée.

Code : Tout sélectionner

« "Calcul des termes de la suite de Fibonacci" DROP
  -> n
   « "Initialise la suite avec F0=0 et F1=1" DROP
     0 n SIGN    
        "^--- une astuce pour le cas où n=0, la somme fera quoi qu'il arrive toujours 0" DROP

     "Boucle principale de 2 à n (si n=0 ou n=1 on fait une fois la boucle" DROP
     "Par chance le résultat avec n=1 est alors valide. Et celui avec n=0 " DROP
     "est garanti par la fonction SIGN" DROP
 
     2 n START
         DUP2 +  "Additionne les deux derniers termes totu en en laissant une copie dans la pile" DROP
     NEXT
     "Fin du programme        " DROP  "C'est chouette ces commantaires en RPL ! Non ?" DROP
   »
»
'FIB' ST'FIB' ST

Ouais, tu enlèves un commentaire tout en oubliant le DROP et t'as un programme qui ne marche plus.

[gege]

Bonjour,
Pour sauver l'honneur de Casio, une version qui consomme une place incroyable (60 octets !) mais qui est rapide. Pour Graph 85 :

FIBONACC
?->N:RndFix(((1+¥5)/2)^N/¥5,0)->F:F

(¥ etant le signe de la racine carree).
Ca calcule F(49)=7778742049 en un temps non mesurable (mais une bete boucle est indecelable de l'instantane aussi).
On a aussi F(68) calcule comme 72723460248157, alors que les deux derniers chiffres devraient etre 41. Pas anormal cependant.
G.E.