Misez p'tit Optimisez n°94 : les nombres de Motzkin

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

Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par Danny »

3 minutes sur HP-42S avec ma version actuelle, pour calculer le 260ème nombre de Motzkin :o
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
gege
Fonctionne à 14400 bauds
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

Message par gege »

Bonjour,
Super car le rapport de puissance est bien supérieur à 25.
J'essaie votre algorithme.
G.E.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
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

Message par C.Ret »

gege a écrit : 10 juil. 2020 20:39 [...]La version à boucle est rapide, permettant de calculer le 260ème nombre de Motzkin en 7 secondes (c'est environ 3.9e120).
Et vos versions ?
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
Et je trouve en quelques 10~11_s secondes que
MZ(260) = 3900191474776594683370868070046397312709086028395092039918926696609510646809205656589823273818271458704292549853287532139.
MPO94 HP Prime M260.png
MPO94 HP Prime M260.png (10.56 Kio) Vu 8531 fois
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.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
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

Message par C.Ret »

Danny a écrit : 10 juil. 2020 22:403 minutes sur HP-42S avec ma version actuelle, pour calculer le 260ème nombre de Motzkin :o
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 :mrgreen:

gege a écrit : 11 juil. 2020 12:57 Bonjour,
Super car le rapport de puissance est bien supérieur à 25.
J'essaie votre algorithme.
G.E.


Pour le moment nous n'avons exploité que trois algorithmes basés sur deux formules permettant le calcul des Nombres de Motskin:
  1. Algorithme récursif direct: également dénommé "fonction récursive très bête" qui consiste à programmer brutalement la définition récursive suivante:
    Image
    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
  2. 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:
    Image
    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.
  3. 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:
    Image
    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.
Mais il existe certainement d'autres algorithmes basés sur des équations différentes certainement plus préformantes. Et je me réjouis déjà par avance de les voir surgir dans les pages de ce forum:
  1. 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:
    Image
    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..
  2. 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.
    Image
    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.
  3. 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.
    Image
    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.
  4. Algorithme direct: solution par un calcul direct ne dépendant que de l'ordre n
    Image
    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).
  5. 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.
    MPO94 Motzkin Number LOG graph.gif
    MPO94 Motzkin Number LOG graph.gif (8.86 Kio) Vu 8485 fois
    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.
Enfin, nos imaginations ne devraient pas avoir de limite...

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
En mode DEF, 23 [shift][M] affiche 23. 1129760415. en 18s
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.
Avatar du membre
gege
Fonctionne à 14400 bauds
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

Message par gege »

Bonjour,
Wow quel exposé ! J'ai une idée pour améliorer l'algorithme belge, en cours de bricolage.
A+
G.E.
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par Danny »

Merci C.Ret pour l’énumération des algos 8)
C’est « l’italien » que j’avais implémenté en 1er sur HP 42S... mais en itératif :geek:

Je le posterai prochainement.
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
gege
Fonctionne à 14400 bauds
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

Message par gege »

Bonjour,
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;
Et voici les résultats des diverses méthodes sur HP Prime, en secondes :

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
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

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
Ca calcule le 50ème terme en 7 secondes sur PC-1475 et 0.5 secondes sur PC-G850.

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
La HP15C Limited Edition donne M(100) en 1.5 seconde.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
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

Message par C.Ret »

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
Image
a été un peu transformée pour réduire la quantité de calcul:
Image avec Image,Image et Image

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.
Avatar du membre
gege
Fonctionne à 14400 bauds
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

Message par gege »

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.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
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

Message par C.Ret »

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.
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par Danny »

Popop y a du niveau les gars :o
Le code de Gege pour HP classique est magnifique 8)

Bon alors moi j’avais raisonné en mode bourrin (comme souvent), en partant de la définition de base :

Image

qui peut s’exprimer comme l’avait précisé ensuite C.Ret :

Image

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 :

Image
Image
Image
Image
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 :

Image
Image
Image
Image
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 :oops:
Par contre petit bonus, à la fin on a tous les nombres de Motzkin dans la matrice REGS (sur HP-42S) ! :mrgreen:

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.
Avatar du membre
gege
Fonctionne à 14400 bauds
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

Message par gege »

Bonjour,
@C.Ret : Ah oui :oops: 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.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
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

Message par C.Ret »

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 :

Image
Image
Image
Image
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 :[...]
Bien vu ! J'avais effectivement commencé de la même façon, mais je n'ai pas vu la symétrie.
enfin, pas cette symétrie, mon esprit tordu comme un alambic d'alchimiste a interprété cette symétrie comme étant un produit scalaire :
Image

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
(Marge, à juste titre, va nous dire que ce code n'est pas clair. Mais non, c'est un bon code RPL. C'est d'ailleurs pour cela que je commente chaque ligne, car sinon dès la semaine prochaine je ne saurai plus ce qu'il fait !)
Danny a écrit : 15 juil. 2020 12:13 [...]Par contre petit bonus, à la fin on a tous les nombres de Motzkin dans la matrice REGS (sur HP-42S) ! :mrgreen:
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.
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par Danny »

Rah pas mal le coup du produit scalaire 8)

Faudrait faire un tableau comparatif des temps de calcul de tous ces algos :geek:
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
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

Message par C.Ret »

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 !
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.
Répondre

Retourner vers « Tous les Pockets »