Misez p'tit Optimisez n°53 : la suite de Syracuse

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
tyann
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 845
Enregistré le : 06 oct. 2012 14:37

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par tyann »

Bonsoir
Ma calculette ne peut pas gérer de liste de plus de 10000 éléments
J'utilise beaucoup les listes depuis quelques temps et donc j'ai testé que :
une liste peut contenir des listes de 9999 éléments
je suis monté jusque 6 listes de plus de 9000 éléments
théoriquement on devrait pouvoir créer une liste de 9999 listes de 9999 éléments (pas testé ) :(
Ti(s) 60, 62 Galaxy, 66, 67 Galaxy, 68, 74 Basical 80, 81, 82, 83+, 83 CE, 84+SE, 85, 86, 89, 89 titanium, 92, 95 Procalc, v200, nSpire cx
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par zpalm »

C.Ret a écrit : Le gain de temps doit provenir de l'utilisation des variables globales et de la fonction FP() dont l'appel doit être plus rapide que les fonctions CAS odd ou even (entre-temps je les ai trouvées, ainsi que le catalogue de toutes les fonctions de ma machine :))
Le passage de l'environnement Home au CAS qui se fait chaque fois que l'on utilise une fonction CAS dans un programme non CAS prend du temps, du coup utiliser FP est plus rapide que odd ou even.
C.Ret a écrit : Par ailleurs si quelqu'un connaît un moyen de supprimer un terme d'une suite sans utiliser DIFFERENCE, et qu'il peut nous l'expliquer, je lui en serai fort reconnaissant.
Je ne connais pas de fonction sur la Prime qui le fasse directement, mais si on veut supprimer l'élément n d'une liste , on peut utiliser la fonction suivante :

Code : Tout sélectionner

EXPORT Suppress(list,n)
BEGIN
LOCAL m:=SIZE(list);
CONCAT(IFTE(n=1,{},list({1,n-1})),IFTE(n=m,{},list({n+1,m})));
END;
Sinon pour ajouter un élément à la fin d'une liste, pas besoin de CONCAT, il suffit d'utiliser l'index 0. Par exemple 5▶L0(0) ajoute 5 à la fin de L0.
Modifié en dernier par zpalm le 03 mars 2017 17:39, modifié 2 fois.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par C.Ret »

Merci zpalm pour ces précisions.

Pour effacer un des éléments d'une liste il n'y a donc pas d'astuce simple, comme y mettre un élément vide ou un truc du genre.
Je garde donc mon idée d'utiliser DIFFERENCE qui me permet de réaliser l'opération sans aucun test.
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
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par zpalm »

C.Ret a écrit :Je garde donc mon idée d'utiliser DIFFERENCE qui me permet de réaliser l'opération sans aucun test.
oui, mais ce n'est pas le plus rapide. Ci-dessous j'ai codé les 2 versions de la fonction de suppression d'un élément d'une liste:
  • Suppress0: ce que tu utilises dans ton programme avec DIFFERENCE
  • Suppress1: ma proposition avec CONCAT
Le programme TestSup(n) créé une liste de n éléments, puis appelle n fois chaque fonction Suppressx pour supprimer successivement chaque élément. Il retourne le temps total de l’opération pour chaque fonction Suppressx.

A essayer avec TestSup(9000) sur l’émulateur et TestSup(2000) sur la calculatrice.

Code : Tout sélectionner

EXPORT Suppress0(list,n)
BEGIN
−1▶list(n);DIFFERENCE(list,−1); 
END;

EXPORT Suppress1(list,n)
BEGIN
LOCAL m:=SIZE(list);
CONCAT(IFTE(n=1,{},list({1,n-1})),IFTE(n=m,{},list({n+1,m})));
END;

te0(n)
BEGIN
FOR I FROM 1 TO n DO Suppress0(L0,I); END;
END;

te1(n)
BEGIN
FOR I FROM 1 TO n DO Suppress1(L0,I); END;
END;

EXPORT TestSup(n)
BEGIN
local t0, t1;
L0:=MAKELIST(I,I,1,n);
t0:=TEVAL(te0(n));
t1:=TEVAL(te1(n));
RETURN {t0,t1};
END;
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par zpalm »

C.Ret a écrit : Par ailleurs si quelqu'un connaît un moyen de supprimer un terme d'une suite sans utiliser DIFFERENCE, et qu'il peut nous l'expliquer, je lui en serai fort reconnaissant.
En fait il y a une bien une fonction pour ça, c'est la fonction suppress du CAS: suppress(list,n) supprime dans une liste l’élément d’indice n, et non comme c'est indiqué de manière erronée dans le guide de l'utilisateur: "supprime la première occurrence de l'élément dans la liste".
Par contre comme c'est une fonction CAS c'est beaucoup plus lent que les solutions discutées précédemment....
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°53 : la suite de Syracuse

Message par gege »

Bonjour,
Et en écrivant un programme 100% CAS ?
G.E.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par C.Ret »

Bonsoir gégé.

Excellente suggestion :

Code : Tout sélectionner

#cas
syr(n):=
BEGIN
 IP(n)▶n▶m;0▶f;TICKS▶t;
 WHILE n>1 DO 1+f▶f; IF even(n) THEN n/2▶n ELSE 3*n+1▶n; MAX(m,n)▶m; END; END;
 return {f,m,(TICKS-t)*.001_(s)};
END;
#end
C'est alors un tantinet plus lent :
Image
Mais tellement plus puissant:
Image
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°53 : la suite de Syracuse

Message par gege »

Bonjour,
Excellent !
Ton idée des valeurs clefs est un bon exemple du dilemne de l'optimisation sur caltos : l'algorithme simpliste est beaucoup plus court, donc passe comparativement beaucoup plus de temps dans les primitives du langage qui sont en langage machine, alors que la version intelligente rame dans les dédales de l'interpréteur.
Pour gagner il faut une méthode qui prenne un raccourci radical dans le nombre d'instructions...
G.E.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par zpalm »

Le CAS est effectivement très puissant, on peut gagner ~20% de temps d'exécution avec l'astuce de caloubugs :

Code : Tout sélectionner

#cas
syr(n):=
BEGIN
 IP(n)▶n▶m;0▶f;TICKS▶t;
 WHILE n>1 DO 
   IF odd(n) THEN 
     3*n+1▶n; MAX(m,n)▶m; 1+f▶f; 
   END; 
   n/2▶n+1; 1+f▶f; 
 END;
 return {f,m,(TICKS-t)*.001_(s)};
END;
#end
EDIT: je viens de tester sur ma Prime et je ne retrouve pas le gain de performance observé sur l'émulateur :(
Avatar du membre
Xerxes
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 292
Enregistré le : 02 avr. 2007 13:41
Localisation : Allemagne
Contact :

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Xerxes »

Not that easy, but possible on the FX-180P using 27 bytes and 4 vars:

Code : Tout sélectionner

 01  2
 02  Kin/1
 03  Kout1
 04  -
 05  1
 06  Kin+3
 07  =
 08  1/x
 09  Kout1
 10  Kin2
 11  FIX0
 12  RND
 13  NORM
 14  Kin-2
 15  .
 16  5
 17  Kin+2
 18  Kout2
 19  x>0
 20  6
 21  Kin*1
 22  1
 23  Kin+1
 24  Kout1
 25  x<=M
 26  Min
 27  RTN
Usage example:

KAC Min 27 Kin1 P1

program stops with error

Kout3 -> 111

MR -> 9232

Edit: Shorter version to fit also in the FX-50F or FX-3400P
Modifié en dernier par Xerxes le 17 mars 2017 14:04, modifié 3 fois.
Avatar du membre
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5631
Enregistré le : 26 mars 2009 13:07
Localisation : Ile de France
Contact :

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par ledudu »

Nice shot !
Avatar du membre
Xerxes
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 292
Enregistré le : 02 avr. 2007 13:41
Localisation : Allemagne
Contact :

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Xerxes »

Slow, slower, TI-62:

Code : Tout sélectionner

 00  1
 01  STO+1
 02  x<->t
 03  2
 04  STO/0
 05  RCL 0
 06  x=t
 07  R/S
 08  FRAC
 09  C.t
 10  x=t
 11  RST
 12  6
 13  STO*0
 14  1
 15  STO+0
 16  RCL 2
 17  x<->t
 18  RCL 0
 19  x>t
 20  STO 2
Usage example:

CM 27 STO 0 RST R/S

RCL 1 -> 111

RCL 2 -> 9232

Execution time: 380 seconds
Avatar du membre
Xerxes
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 292
Enregistré le : 02 avr. 2007 13:41
Localisation : Allemagne
Contact :

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Xerxes »

Assembly language routine for the PB-1000 series for large numbers up to 16 digits in BCD format.
Most of the instructions are not supported by the built-in assembler of the PB-1000.

Code : Tout sélectionner

@00: ADW   $24,#1
     LDL   $8,$0,L8
     ADBL  $0,$8,L8
     ANC   $8,#1
     JR    NZ,@01
     ADBL  $8,$0,L8
     ADBL  $0,$8,L8
     DIDL  $7,L8
     XRC   $0,#1
     JR    NZ,@00
     ANCL  $1,$1,L7
     RTN   Z
     JR    @00
@01: ADBL  §0,$8,L8
     ADBL  $0,1,L8
     SBBCL $16,$0,L8
     JR    NC,@00
     LDL   $16,$0,L8,J.@00
Input: N in registers $0-$7

Output: maximum in registers $16-$23 as BCD and steps in registers $24/25 as binary

Execution time for 77031: 0.108. seconds
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°53 : la suite de Syracuse

Message par dprtl »

Xerxes a écrit :Assembly language routine for the PB-1000 series for large numbers up to 16 digits in BCD format.
Most of the instructions are not supported by the built-in assembler of the PB-1000.
Very impressive demonstration ! One day, will you publish some "educational content" about all your discoveries on the Casio PB-1000 ? About the HD61700 product line, assembly langage, and tools ? Wikipedia content is still very poor, and a lot of links, in the vintage Casio calculators sphere, tend to become broken.
Avatar du membre
Xerxes
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 292
Enregistré le : 02 avr. 2007 13:41
Localisation : Allemagne
Contact :

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Xerxes »

Salut Daniel,

merci for your kind words. The HD61700 is a highly interesting CPU with a very nice and special instruction set. Unfortunately the
PB-1000 assembler contains a subset of these instructios only. What I miss particularly, are the instructions for LCD access and
the multi byte commands, that allows to handle up to 64 bit in 8 bit steps at once. Something similar is also available on the SHARP
CPUs, but by far not that consequent. This concept allows interesting solutions in some cases and a significant speed gain too.
I've send all my discoveries regarding the HD61700 to Piotr, for having his excellent PB-1000/PB-2000C emulator, as accurate as
possible. You will find all about the PB-1000 on his site. Some HD61700 tools are available here.
Please notice, that I use different mnemonics for the undocumented instructions. I think the ones in the documentations are the
creaton of some Japanese while reverse engineering. The ones I use, are the original mnemonics that CASIO used to develop
the HD61700 based pockets.

Pascal
Répondre

Retourner vers « Tous les Pockets »