Misez p'tit Optimisez n°94 : les nombres de Motzkin
Modérateur : Politburo
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
3 minutes sur HP-42S avec ma version actuelle, pour calculer le 260ème nombre de Motzkin
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
- gege
- Fonctionne à 14400 bauds
- Messages : 7141
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
Bonjour,
Super car le rapport de puissance est bien supérieur à 25.
J'essaie votre algorithme.
G.E.
Super car le rapport de puissance est bien supérieur à 25.
J'essaie votre algorithme.
G.E.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3405
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
Ah! Oui, merci gégé, je n'ai pas pensé à faire un programme dans l'éditeur de la touche (Shift)[ 1 ]
Du coup je choisi la plus rapide:
Code : Tout sélectionner
#cas /* Mode C.A.S. ON : entiers longs sans limite
MZ(n):=
BEGIN /* Pré-allocation mémoire: construction de la liste
LOCAL i,m:=MAKELIST(k<2,k,0,n); /* m:={ 1 1 0 0 ... 0 } contenant (n+1) éléments
FOR i FROM 2 TO n DO m[1+i]:=m[i]+sum(m[j]*m[i-j],j,1,i-1) END; /* Calcul itératif par pré-mnémonization dans m[i]
m[1+n]
END; /* renvoie MZ(n):=m[1+n]
#end
MZ(260) = 3900191474776594683370868070046397312709086028395092039918926696609510646809205656589823273818271458704292549853287532139.
Bon en réalité, le code ci-dessus est mon code original amélioré grâce aux codes donnés par gégé; je me suis rendu compte que j'avais insérer un block IF THEN ELSE END; inutile, la boucle FOR FROM TO END; ne s'exécutant pas pour n<2 !
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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3405
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
Je n'ai pas essayé sur mon HP-15C, elle ne peut calculer au-delà de 9,999999999 E+99
De plus, il lui faut pas moins de 48 secondes pour déterminer que M25 = 9'043'402'501 qui est le plus grand nombre de MotzKin qu'elle peut déterminer précisément.
Par ailleurs, le calcul de M100 affiche 7,374155 E+44 après un run de 10min50s.
Les temps de calculs des Mn n'étant pas une fonction affine de l'indice n, j'imagine que mon HP-15C pourrait mettre plus de 15min pour calculer M260 et n'afficher qu'un 9,999999 99 clignotant
Pour le moment nous n'avons exploité que trois algorithmes basés sur deux formules permettant le calcul des Nombres de Motskin:
- Algorithme récursif direct: également dénommé "fonction récursive très bête" qui consiste à programmer brutalement la définition récursive suivante:
Il faut bien évidemment une calculatrice performante et rapide, car le simple calcul de Mn(10) nécessite pas moins de 4843 appels de ladite fonction - Algorithme récursif par mnémonisation: basé sur la même définition récursive; il permet un calcul de Mn bien plus rapide en mémorisant toutes les valeurs de M0 à Mn:
Cet algorithme est bien plus facile à implémenter sur toutes calculatrices et pockets ayant suffisamment de mémoire. Mais ce n'est peut-être pas le plus rapide à déterminer les grands nombres de Motzkin. En effet, le nombre de multiplications à effectuer augmente de façon linéaire avec n et donc les temps de calculs augmentent exponentiellement. - Algorithme itératif belge par Nombres de Catalan : basé sur la relation qui existe entre les Nombres de Motzkin, les coeffcients binomiaux et les Nombres de catalan, ce calcul de Mn limite le nombre des itérations à n/2:
Cet algorithme sera plus facile à implémenter sur les calculettes car il ne nécessite pas de mémoriser une liste ou un tableau.
En outre, le nombre limité d'itérations le rend également plus efficace pour les grands indices n ou les machines lentes car le temps de calcul varie d'une façon plus linéaire. par contre, il ne sera efficace et performant que sur les machines possédant une fonction native Cx,y ou COMB de calcul de ces coefficients binomiaux.
Sur les machines dépourvues, la programmation d'un calcul efficace des coefficients binomiaux va vite rendre cet algorithme fort déplaisant, long, complexe et très lent.
- Algorithme italien récursif de proche en proche: calcul récursif basé sur la relation qu'il existe entre un Nombre de Motskin Mn d'ordre n et les deux nombres qui le précèdent aux ordres n-1 et n-2:
Cette relation ressemble beaucoup à la définition habituellement utilisée pour la suites des Nombres de Fibonacci. L'implémentation de cet algorithme ne nécessite pas de mémoriser de listes de nombres et sera donc facile à implémenter sur des machines ayant peu de mémoire (comme les TI-57 LCD).
Le même calcul est effectué de proches en proches et donc le temps de calcul des grands nombres de Motzkin sera une fonction affine de l'ordre n y compris pour les machines ne pouvant déterminer efficacement les coefficient binomiaux.. - Algorithme triangulaire:En observant la façon dont sont construit les Triangles de Motskin dont un exemplaire est donné ci-dessous, il est facile de trouver un algorithme qui permet de déterminer les Nombres de Motskin qui se trouvent être à l'extrémité de chaque ligne.
Comme pour le Triangle de Pascal, il est possible de déduire chaque terme d'une ligne à partir de termes pris sur la ligne précèdente. Dans le cas des Traingle de Motskin, chaque élément peut être déduit en effectuant la somme des trois éléments se trouvant juste au-dessus à gauche dans la ligne précédente. Par exemple 147 = 8 + 35 + 104 ou 2188 = 1353 + 835 + 0.
Cet algorithme pourrait être exploité sur des machines ayant un adressage indirect et une pile opérationnelle. Notons que tout le Triangle de Motzkin n'a besoin d'être mémorisé. Uniquement une ligne qui serait modifiée dynamiquement. - Algorithme direct paramétrique: basé sur la relation entre le Nombre de Motzkin Mn d'ordre n et les deux nombres de Motzkin initiaux M0 et M1.
Malheureusement, pour le moment personne ne semble avoir déterminée cette relation. Mais je ne suis pas inquiet, il pourrait y avoir parmi nous des inventeurs suffisamment adroits pour en proposer une et la programmer du bout des doigts sur un de leurs sascefaitplus. - Algorithme direct: solution par un calcul direct ne dépendant que de l'ordre n
Ce serait la solution idéale pour nos calculettes. Malheureusement à l'heure où j'édite ce massage personne en semble avoir eut l'audace d'expliciter cette fonction ! (Mais je suis serein et confiant cela ne va plus tarder). - Autres Solutions: comme la liste des Nombre de Motzkin est publique et disponible sur Internet, comme par exemple OEIS A001006. Rien ne nous empêche d'écrire un code qui va chercher son résultat sur le Réseau des Réso.
Ou à défaut de connexion sur nos Pocket antédiluviens, de déterminer par régression diophantienne une valeur approchée qui par arrondi (tous les Nombres de Motzkin sont des entiers) donnerai à défaut du nombre Mn, un intervalle raisonnable. Sans compter les implémentations où une liste plus ou moins longue des Nombres de Motzkin serait comprimée dans une carte RAM sauvegardée par une pile lithium et une petit code sympathique et performant permettrait d'extraire un quelconque nombre Mn.
Voici par exemple un one-liner pour SHARP PC-1211 basé sur l'algorithme(a) italien:
Code : Tout sélectionner
1:"M"AREAD N:A=0,M=2:FOR K=2 TO N+2:B=3A+M,A=M,M=M+B+3B/K:NEXT K:PRINT N,M:END
Modifié en dernier par C.Ret le 12 juil. 2020 15:35, modifié 4 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.
- gege
- Fonctionne à 14400 bauds
- Messages : 7141
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
Bonjour,
Wow quel exposé ! J'ai une idée pour améliorer l'algorithme belge, en cours de bricolage.
A+
G.E.
Wow quel exposé ! J'ai une idée pour améliorer l'algorithme belge, en cours de bricolage.
A+
G.E.
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
Merci C.Ret pour l’énumération des algos
C’est « l’italien » que j’avais implémenté en 1er sur HP 42S... mais en itératif
Je le posterai prochainement.
C’est « l’italien » que j’avais implémenté en 1er sur HP 42S... mais en itératif
Je le posterai prochainement.
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
- gege
- Fonctionne à 14400 bauds
- Messages : 7141
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
Bonjour,
On peut réécrire l'algorithme Belge avec une boucle pour éviter le calcul de combinaisons, ça accélère pas mal :
Et voici les résultats des diverses méthodes sur HP Prime, en secondes :
Ca a sacrément accéléré avec la méthode Belge !!
Mais des erreurs s'accumulent, par exemple M(20) par cette méthode donne 50852018.9998
Excellent MPO !
G.E.
EDIT : une version BASIC
Ca calcule le 50ème terme en 7 secondes sur PC-1475 et 0.5 secondes sur PC-G850.
Version HP classique (39 pas) :
La HP15C Limited Edition donne M(100) en 1.5 seconde.
On peut réécrire l'algorithme Belge avec une boucle pour éviter le calcul de combinaisons, ça accélère pas mal :
Code : Tout sélectionner
EXPORT motzkin6(n)
BEGIN
LOCAL a,p,q,k,m;
1►a;n+2►p;n+3►q;1►k;1►m;
WHILE 2*k<=n DO
a*(p/k-2)►a;k+1►k;a*(q/k-2)►a;m+a►m;
END;RETURN m;
END;
Code : Tout sélectionner
n 10 50 100 260
1 1.7 - - - récursion (trop lent au-delà de 20)
2 0.02 0.3 1 9.7 "récursif" avec mémorisation
3 0.09 0.8 2.8 20 "récursif" avec mémorisation version CAS mode Home
3* 0.12 1 3 20 "récursif" avec mémorisation version CAS mode CAS
4 0.003 0.02 0.04 0.1 réccurence à deux termes
5 0.001 0.008 0.03 0.16 belge avec combinaisons
6 0.004 0.02 0.03 0.07 belge avec boucle
Mais des erreurs s'accumulent, par exemple M(20) par cette méthode donne 50852018.9998
Excellent MPO !
G.E.
EDIT : une version BASIC
Code : Tout sélectionner
100 REM --- MOTZKIN
110 WAIT 0:INPUT "Motzkin(n) n=";N
120 A=1:K=1:M=1:P=N+2:Q=N+3
130 IF 2*K>N THEN 150
140 A=A*(P/K-2):K=K=1:A=A*(Q/K-2):M=M+A:GOTO 130
150 PRINT "Motzkin(";N;")=";M:END
Version HP classique (39 pas) :
Code : Tout sélectionner
LBL A
STO 1
1 STO 2 STO 5 STO 6
+ 1 + STO 3
1+ STO 4
LBL 1
RCL 1 RCL 5 2 *
TEST 7 (x>y)
GTO 2
RCL 3 RCL 5 / 2 - STO* 2
1 STO+ 5
RCL 4 RCL 5 / 2 - STO* 2
RCL 2 STO+ 6
GTO 1
LBL 2
RCL 6
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3405
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
J'attends avec impatience la version "italienne" promise par danny
Je suis un curieux invétéré !
Pour le moment je n'utilise cet algorithme que sur mon SHARP PC-1211:
L'équation donnant l'expression des Nombre de Motzkin
a été un peu transformée pour réduire la quantité de calcul:
avec , et
Astuce supplémentaire, pour calculer Mn, on effectue une boucle sur k dans laquelle les variables A et M mémorisent respectivement les valeurs de M(k-2) et M(k-1). On calcule alors B puis M est copiée dans A et la nouvelle valeur M(k) est mémorisée dans la variable M. On est ainsi prêt pour le tours de boucle suivant, ou en fin de calcul, à afficher M(n) à partir de M.
D'où les codes respectifs :
Je suis un curieux invétéré !
Pour le moment je n'utilise cet algorithme que sur mon SHARP PC-1211:
L'équation donnant l'expression des Nombre de Motzkin
a été un peu transformée pour réduire la quantité de calcul:
avec , et
Astuce supplémentaire, pour calculer Mn, on effectue une boucle sur k dans laquelle les variables A et M mémorisent respectivement les valeurs de M(k-2) et M(k-1). On calcule alors B puis M est copiée dans A et la nouvelle valeur M(k) est mémorisée dans la variable M. On est ainsi prêt pour le tours de boucle suivant, ou en fin de calcul, à afficher M(n) à partir de M.
D'où les codes respectifs :
Code : Tout sélectionner
1 "M"AREAD N:A=0,M=2:FOR K=2 TO N+2:B=3A+M,A=M,M=M+B+3B/K:NEXT K:PRINT N,M:END
Code : Tout sélectionner
EXPORT MZ(n)
BEGIN
LOCAL a:=0,b,k,m:=2;
FOR k FROM 2 TO 2+n DO m+(3*a+(m▶a)▶b)-3*b/k▶m END;
RETURN m;
END;
Code : Tout sélectionner
:MZ(n)
:Func
: Local a,b,k,m : 0→a : 2→m
: For k,2,2+n
: m+3a→b : m→a : a+b-3b/k→m
: EndFor
: Return m
:EndFunc
Code : Tout sélectionner
« → n « 2 0
2 n 2 + FOR k
3 * OVER + DUP2 + 3 ROT * k / + SWAP
NEXT DROP » »
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.
- gege
- Fonctionne à 14400 bauds
- Messages : 7141
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
Bonjour,
Oulà ça fait longtemps que je n'avais pas vu du code Nspire !
Quelle est la vitesse sur cette machine par rapport à la HP Prime ?
Le 260 ème nombre de Motzkin est trouvé en 0.08 s sur cette dernière.
Pas mal l'algorithme.
G.E.
Oulà ça fait longtemps que je n'avais pas vu du code Nspire !
Quelle est la vitesse sur cette machine par rapport à la HP Prime ?
Le 260 ème nombre de Motzkin est trouvé en 0.08 s sur cette dernière.
Pas mal l'algorithme.
G.E.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3405
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
Sur N-Spire je sais pas, mais sur ma Ti-92 II le calcul donne tous les chiffres en environ 16s
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.
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
Popop y a du niveau les gars
Le code de Gege pour HP classique est magnifique
Bon alors moi j’avais raisonné en mode bourrin (comme souvent), en partant de la définition de base :
qui peut s’exprimer comme l’avait précisé ensuite C.Ret :
et que j’avais commencé à développer pour exprimer chaque nombre de Motzkin en fonction des nombres de Motzkin précédents, pour les 1ers indices, histoire de voir à quoi ça ressemblait :
etc.
puis simplifié selon la symétrie des produits, où on voit qu'il y a 2 cas différents selon la parité de l'indice du nombre de Motzkin :
etc.
Du coup j’ai tout simplement codé ça en mode itératif, avec une boucle principale qui calcule tous les nombres de Motzkin à partir de M(3) jusqu’à celui demandé, en conservant chaque nombre de Motzkin dans un registre correspondant à l’indice du nombre en question (R0 = M(0), R1 = M(1), etc.). Donc évidemment, on est limité par le nombre de registres dispos... sur une vraie HP-42S par exemple ça dépend du nombre d'autres programmes qu'on a déjà en mémoire (sur Free42 on est plus à l'aise par contre ).
Bref c’est pas vraiment optimisé, surtout comparé aux vôtres
Par contre petit bonus, à la fin on a tous les nombres de Motzkin dans la matrice REGS (sur HP-42S) !
Voilà donc la bête sur HP-42S :
Le code de Gege pour HP classique est magnifique
Bon alors moi j’avais raisonné en mode bourrin (comme souvent), en partant de la définition de base :
qui peut s’exprimer comme l’avait précisé ensuite C.Ret :
et que j’avais commencé à développer pour exprimer chaque nombre de Motzkin en fonction des nombres de Motzkin précédents, pour les 1ers indices, histoire de voir à quoi ça ressemblait :
etc.
puis simplifié selon la symétrie des produits, où on voit qu'il y a 2 cas différents selon la parité de l'indice du nombre de Motzkin :
etc.
Du coup j’ai tout simplement codé ça en mode itératif, avec une boucle principale qui calcule tous les nombres de Motzkin à partir de M(3) jusqu’à celui demandé, en conservant chaque nombre de Motzkin dans un registre correspondant à l’indice du nombre en question (R0 = M(0), R1 = M(1), etc.). Donc évidemment, on est limité par le nombre de registres dispos... sur une vraie HP-42S par exemple ça dépend du nombre d'autres programmes qu'on a déjà en mémoire (sur Free42 on est plus à l'aise par contre ).
Bref c’est pas vraiment optimisé, surtout comparé aux vôtres
Par contre petit bonus, à la fin on a tous les nombres de Motzkin dans la matrice REGS (sur HP-42S) !
Voilà donc la bête sur HP-42S :
Code : Tout sélectionner
LBL "Motzkin"
CLRG
STO n
1000
/
3
+
STO c
1
STO 00
STO 01
2
STO 02
LBL 01 // boucle de parcours des termes de 3 à celui demandé
0
STO i
STO r
RCL c
IP
2
-
STO j
LBL 02 // boucle de calcul des produits
RCL IND i
RCL IND j
*
2
*
STO+ r // ajoute le calcul courant au total
1
STO- j // décrémente j d'abord
RCL j
RCL i
X=Y?
GTO 03 // si i = j, interrompt la boucle (cas où n est impair)
1
STO+ i // incrémente i ensuite
RCL i
RCL j
X=Y?
GTO 03 // si i = j, interrompt la boucle (cas où n est pair)
GTO 02
LBL 03
RCL c
IP
2
MOD
X<>0?
GTO 04
RCL IND i // si n est pair, ajoute le dernier produit (avec i = j)
RCL IND j
*
STO+ r
LBL 04
1 // ajoute M(c-1)
STO- n
RCL IND n
STO+ r
RCL r
STO IND c // stocke M(c)
ISG c
GTO 01
n : indice du nombre à calculer
c : compteur de boucle
i : indice du nombre de Motzkin M(n-2)
j : indice du nombre de Motzkin M(n-1)
r : accumulateur des calculs intermédiaires du nombre de Motzkin en cours
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
- gege
- Fonctionne à 14400 bauds
- Messages : 7141
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
Bonjour,
@C.Ret : Ah oui c'est pour TI92/89...
@Danny : Excellent, à voir si on peut gratter des octets. Ta méthode est celle "par mémorisation".
Je me demande sur quelle machine ce serait amusant de faire tourner le bazar ?
Une émulation TI58 (je n'ai plus cette machine dispo là tout de suite ) ?
Une fx-180P ?
Tiens sur Forth/TI89 !! J'y vais. Dur dur…
G.E.
@C.Ret : Ah oui c'est pour TI92/89...
@Danny : Excellent, à voir si on peut gratter des octets. Ta méthode est celle "par mémorisation".
Je me demande sur quelle machine ce serait amusant de faire tourner le bazar ?
Une émulation TI58 (je n'ai plus cette machine dispo là tout de suite ) ?
Une fx-180P ?
Tiens sur Forth/TI89 !! J'y vais. Dur dur…
G.E.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3405
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
Bien vu ! J'avais effectivement commencé de la même façon, mais je n'ai pas vu la symétrie.Danny a écrit : ↑15 juil. 2020 12:13 [...] j’avais commencé à développer pour exprimer chaque nombre de Motzkin en fonction des nombres de Motzkin précédents, pour les 1ers indices, histoire de voir à quoi ça ressemblait :
etc.
puis simplifié selon la symétrie des produits, où on voit qu'il y a 2 cas différents selon la parité de l'indice du nombre de Motzkin :[...]
enfin, pas cette symétrie, mon esprit tordu comme un alambic d'alchimiste a interprété cette symétrie comme étant un produit scalaire :
Comme on peut le voir, chaque nouveau nombre de Motzkin est obtenu directement en effectuant le produit scalaire de deux vecteurs symétriques A et B dont on ajoute un nouveau terme au début de B ou à la fin de A.
Cela a inspiré à mon esprit délirant (mais imaginatif) un code pour HP-28C/S en utilisant l'instruction DOT. Malheureusement, l'HP-28C/S ne possède pas d'instruction d'inversion (ou de décalage) des listes ou des vecteurs. Le plus simple est donc de construire les listes A et B au fur et à mesure. En laissant les listes A et B sous forme de liste pour faciliter l'ajout des termes mais qui nécessite de convertir à chaque fois en vecteur pour effectuer le produit scalaire !
Ce qui donne le code suivant pour HP-28C/S:
Code : Tout sélectionner
« → n « { 1 } DUP 1 //* Initialise les listes A et B et le premier nombre (M0 ou M1 )
IF n 2 ≥ THEN //* Evite la boucle START/.../NEXT lorsque n est 0 ou 1
2 n START
ROT + //* Ajoute le nouveau nombre en début de la liste B et
SWAP OVER 2 GET + //* augmente A d'un terme à droite (pris dans B)
OVER LIST→ →ARRY //* Converti la liste B en vecteur et
OVER LIST→ →ARRY DOT //* converti la liste A et effectue le produit scalaire A.B
NEXT //* ce qui donne directement le nombre suivant
END
ROT ROT DROP2 » » //* Remet en ordre la pile pour effacer les deux listes A et B
c'est loin d'être un petit bonus, c'est en fait très important ! Et comme le montre le code que j'ai retranscris ci-dessus, je n'y ai pas non plus pensé immédiatement : l'instruction DROP2 en fin de programme détruit les deux versions (de sens inversé) des listes contenant justement tous les Nombres de Motzkin comme le fait les REGS à la fin du programme de Danny.
Pauvre de moi ...
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.
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
Rah pas mal le coup du produit scalaire
Faudrait faire un tableau comparatif des temps de calcul de tous ces algos
Faudrait faire un tableau comparatif des temps de calcul de tous ces algos
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3405
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin
C'est une bonne idée.
Ce qui est clair est que le code tel que composé dans mon message précédent n'est pas particulièrement rapide. L'éventuel gain de temps à réaliser les produit par l'instruction DOT est largement perdu en accroissement des listes et conversion en vecteurs.
A titre d'exemple, la valeur approchée de M260 est calculée en plus de 30min sur une HP-28S.
Je cherche à éviter les conversions. Une bonne idée aussi est de pré-dimensionner les deux vecteurs A et B pour éviter les réarrangement mémoire dans la boucle de calcul.
Malheureusement, il faut à chaque fois inverser l'ordre dans l'un des deux vecteurs. Je bloque !
Ce qui est clair est que le code tel que composé dans mon message précédent n'est pas particulièrement rapide. L'éventuel gain de temps à réaliser les produit par l'instruction DOT est largement perdu en accroissement des listes et conversion en vecteurs.
A titre d'exemple, la valeur approchée de M260 est calculée en plus de 30min sur une HP-28S.
Je cherche à éviter les conversions. Une bonne idée aussi est de pré-dimensionner les deux vecteurs A et B pour éviter les réarrangement mémoire dans la boucle de calcul.
Malheureusement, il faut à chaque fois inverser l'ordre dans l'un des deux vecteurs. Je bloque !
Modifié en dernier par C.Ret le 17 juil. 2020 13:31, 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.