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

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
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

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

Message par Schraf »

En 8 pas sur Ti-57 LED

Code : Tout sélectionner

LRN

00 01	1
01 32 7	STO 7
02 15	CLR
03 86 0	Lbl 0
04 75	+
05 81	R/S
06 22	x <> t
07 51 0	GTO 0

LRN
RST R/S R/S R/S... affiche 0, 1, 1, 2, 3, 5...
Et même version pour Ti-58/59 :

Code : Tout sélectionner

000 01	1
001 42	STO
002 00	00
003 25	CLR
004 76	Lbl
005 11	A
006 85	+
007 91	R/S
008 48	Exc
009 00	00
010 61	GTO
011 11	A
Avatar du membre
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3626
Enregistré le : 06 sept. 2011 14:57
Localisation : Normandie

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

Message par Hobiecat »

Schraf a écrit : 03 mars 2022 08:56 En 8 pas sur Ti-57 LED
C'est très bien, mais ça ne répond plus à l'énoncé initial. :wink:
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

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

Message par Schraf »

@Hobiecat, après 10 ans je pensais qu'il y avait prescription 😂
Avatar du membre
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3626
Enregistré le : 06 sept. 2011 14:57
Localisation : Normandie

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

Message par Hobiecat »

Schraf a écrit : 03 mars 2022 14:20 @Hobiecat, après 10 ans je pensais qu'il y avait prescription 😂
Oui, bien sûr, il y a prescription.
Mais c'était juste pour noter que ces 8 pas ne font pas mieux que les 10 pas de Badaze en page précédente. :wink:
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

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

Message par Schraf »

En mea-culpa d'avoir oublié qu'il y avait un paramètre en entrée, voici une nouvelle version en assembleur pour les calculatrices Ti-83 Plus (anciennes générations) :

Code : Tout sélectionner

#include    "ti83plus.inc"
#define     progStart   $9D95
.org        progStart-2
.db         $BB,$6D
    bcall(_RclAns)	; Ans -> OP1
    bcall(_ConvOp1)	; OP1 -> DE
    ld hl,0		; HL = 0
    ld b,e
    cp 0		; A = 0 ?
    jp z,fin		; Si oui -> fin
    ld de,$1		; DE = 1
loop: 
    add hl,de		; HL = HL + DE
    ex de,hl		; Echange HL et DE
    djnz loop
fin:
    bcall(_dispHL)	; Affichage de HL
    ret
F(0)=0, F(1)=1, F(16)=987
F(0)=0, F(1)=1, F(16)=987
fibo.png (5.1 Kio) Vu 3638 fois
Ce programme fonctionne jusqu'à F(24) = 46368 qui est la dernière valeur <= 65535

Démonstration en vidéo

Code : Tout sélectionner

PROGRAM:FIBO
:AsmPrgmBB6DEFD7
4AEFEF4A21000043
FE00CAAB9D110100
19EB10FCEF0745C9
40 octets en version compilée ou 71 octets pour la version ci-dessus.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

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

Message par Schraf »

Je n'ai pas vu de version utilisant les puissances de la matrice M = [[1, 1], [1, 0]]. F(n) est le nombre en haut à gauche de la matrice M^(n-1). Pour la HP-50g ça donnerait :

Code : Tout sélectionner

<< 1 - [[1,1][1 0]] SWAP ^ 1 GET >>
'F STO

49 F
7778742049 (résultat quasi instantané)

0 F
0

2395 F	(valeur max pour avoir un résultat cohérent... mais faux puisque la vraie valeur est 9.266713930645145E499)
9.26671393077E499
La matrice peut également être crée par :

Code : Tout sélectionner

2 IDN 1 CON 4 0 PUT
Ce qui signifie : Créer matrice identité 2*2, la remplir de 1 et mettre un 0 à la 4e position. D'où :

Code : Tout sélectionner

<< 1 - 2 IDN 1 CON 4 0 PUT SWAP ^ 1 GET >>
Modifié en dernier par Schraf le 06 mars 2022 09:54, modifié 2 fois.
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

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

Message par dprtl »

Voici une petite version en Basic 1000D (1990) triviale et économe en ressources ; mais capable d'écrire rapidement dans un fichier sur disquette les 4182 chiffres de f(20001) :

Code : Tout sélectionner

input "Fibo?";n
a=0
b=1
for i=1,n-1
  vadd a,b
  exg a,b
next
open "o",#1,"mpo16res.txt"
print #1,b
print #1,"f(";n;")";len(b);" chiffres"
close
Le résultat : mpo16res.txt

Le plus grand nombre que l'on peut calculer avec ce programme (Basic interprété) se situe autour de f(94360) avec 19720 chiffres calculés en 25 minutes environ (1040 ST à 8 MHz).
Modifié en dernier par dprtl le 06 mars 2022 17:17, modifié 1 fois.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

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

Message par Schraf »

@dprtl : Pour avoir F(0) = 0 et non pas F(0) = 1 comme le fait ton programme, je pense que :

Code : Tout sélectionner

a=1
b=0
for i=0,n-1
  vadd a,b
  exg a,b
next
devrait fonctionner, en tous cas ça marche sur la NUMWORKS :

Code : Tout sélectionner

def f(n):
  a, b = 1, 0
  for _ in range(n): a, b = a + b, a
  return b
  
>> f(0)
0
>> f(1)
1
>> f(2)
1
>> f(3)
2
>> f(20001)
4095506670842125091974920367593350749928407432658401162133175259395893585612975134357631357967902147741114726016298221741520831121309138199664825864187854501328120122 ... 82048749390382177080100224710626
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

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

Message par dprtl »

Merci @Schraf pour la correction de bug ! J'en ai aussi un autre sur le calcul du nombre de chiffres du résultat (2 de trop).

Une question hors sujet : la Numworks est une calculette moderne très intéressante pédagogiquement parlant, mais est-ce que ses spécifications sur la mémoire RAM ne sont pas un peu justes pour Python ? Les modèles 2017 et 2019, basés respectivement sur les microcontrôleurs STM32F412 et STM32F730 (si j'en crois certains forums) n'embarquent en effet que 256 Ko de RAM, dont seulement 32 Ko affecté au heap Python par le firmware officiel. Cette dernière valeur ne bride-t-elle pas un peu trop les utilisateurs ?
Modifié en dernier par dprtl le 06 mars 2022 19:55, modifié 1 fois.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

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

Message par Schraf »

@dprtl : Je ne connais pas assez la partie technique de la NW pour répondre correctement mais il est vrai que j'ai des messages du type MemoryError : memory allocation failed. Je trouve cette machine vraiment très agréable, simple et rapide. Mais comme tout le monde je regrette le bridage des dernières mises à jour et que l'on ne puisse pas la programmer en assembleur ou du moins en autre chose que du Python.
Avatar du membre
Schraf
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 499
Enregistré le : 05 mars 2020 20:45
Contact :

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

Message par Schraf »

Vu hier dans l'émission LEGO Masters

Image
Répondre

Retourner vers « Tous les Pockets »