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

[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é )

[zpalm]

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.

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.

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

[zpalm]

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;

[zpalm]

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

[gege]

Bonjour,
Et en écrivant un programme 100% CAS ?
G.E.

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

Mais tellement plus puissant:

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

[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

[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

[ledudu]

Nice shot !

[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

[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

[dprtl]

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.

[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