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
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

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

Message par Gilles59 »

Une autre version en RPL (Edit version amélioré en relisant le topic)

Code : Tout sélectionner

«
 0 OVER
 DO
  SWAP 1 +   
  UNROT 
  DUP 2 MOD   « 3 * 1 + SWAP OVER MAX » « 2 / SWAP » IFTE
  UNROT 
 UNTIL DUP 1 == END  
 DROP 2 ->LIST
»
8400511 donne { 159424614880 , 685 }
Temps :
- RPL : Mode exact 45,9" sec, mode Approx 6,9"
- 0,499 sec en NewRPL

NewRPL only (possible en mode exact en UserRPL mais très lent genre 200 fois plus lent, même mon émulateur PC HP50g est plus lent que la calculatrice physique!)
Syr(75128138247) est calculé en 0,529sec
Syr(12345678901234567890) calculé en 0,569 sec ( avec 32 chiffres significatif ce qui laisse de la marge, mais idéalement il faudrait ajouter un test de débordement pour ne pas dépasser GETPREC ALOG. Ca ralentit assez peu le fonctionnement.

On constate que le NewRPL semble proportionellement plus rapide pour les 'grands nombres que pour les petits. Ca tient à 2choses :
- Les premieres 500ms d'exécution d'un programme se font toujours en vitesse lente (6Mhz) pour économiser les piles puis passage à 192MHz. Je trouve que c'est bien vu car une réponse en 1/2s ou 1/100 de sec ne change pas grand chose pour l'utilisateur. SYR(8400511) est d'ailleurs le pire des cas de ce point de vu, toute la séquence étant calculée à 6MHz (vs 75 MHz pour la HP50G standard)
- La précision par défaut est de 32 chiffres, on peut la baisser mais ce ne fait pas gagner de vitesse. l'augmenter en fait perdre relativement peu

Le code reste très optimisable à la lecture du topic !

EDIT 12345678901234567890123 donne une altitude remarquable (ou est ce un overflow ? ca donne quoi sur la Prime ?)
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
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 »

Sur Hp prime, je trouve:
MPO53.syr2.png
MPO53.syr2.png (9.08 Kio) Vu 14942 fois
en utilisant:

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
Comme d'ailleurs sur TI 92 II (mais il faut un peu plus de temps ~18 s.)

Code : Tout sélectionner

:syr(n)
:Func
:Local f,m
:int(n)→m :0→f
:While n>1
:   1+f→f: If mod(n,2)=0 Then :n/2→n: Else :3*n+1→n:max(n,m)→m: EndIf
:EndWhile
:Return [[f,m]]
:EndFunc

Code : Tout sélectionner

▪syr(12345678901234567890123)
           [575 55555555055555555505556]
Ce qui tend à prouver que ce n'est pas une overflow :D
Modifié en dernier par C.Ret le 15 mars 2020 19:19, 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.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

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

Message par Gilles59 »

C.Ret a écrit : 25 oct. 2017 18:28 Sur Hp prime, je trouve:
Image
Ce qui tend à prouver que ce n'est pas une overflow :D
En effet, même résultat en 0,58" dont 0,5" à se trainer à 6MHz ;D
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2918
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 : 25 oct. 2017 18:28 Sur Hp prime, je trouve:
Image
en utilisant:

Code : Tout sélectionner

#cas
SYR(n):=
BEGIN
  IP(n)►n►m;0►f;TICKS►t;
  WHILE n>1 DO 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
Sur ma HP Prime avec ce programme CAS* j'ai le même résultat mais plus rapidement: environ 0,6s.

*après avoir ajouté f+1►f dans la boucle WHILE.
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 »

Ah oui! Le code " f+1->f; " a disparu lors de l'édition de mon message (en remplaçant manuellement les petites flèches ??) !

Quand au temps d'exécution, il peut y avoir une fuite de temps lié au fait que mon HP prime était connecté par USB au 'Kit' sur mon portable ?
Bizarre !

Quel paramètre peut bien avoir un tel effet ?
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.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

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

Message par Gilles59 »

Sur ma prime, je trouve le même temps que zpalm. Programme saisi directement sur la calc et non connecté en USB. Le ralentissement vient probablement de là : à tester. J'ai essayé de sortir le calcul du temps du programme et d'utiliser TEVAL comme sur la 50G mais ca me renvoie 0_s. TEVAL ne fonctionne pas en CAS?


Si les couleurs des touches de la nouvelle version de la prime sont mieux que l'ancienne, l'orange fluo reste vraiment pas terrible. C'est dommage, encore un effort HP, virez nous cet affreux orange sur fond blanc!
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2918
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

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

Message par zpalm »

Gilles59 a écrit : 26 oct. 2017 11:46TEVAL ne fonctionne pas en CAS?
En mode CAS, essaye avec time au lieu de TEVAL.
C.Ret a écrit : 26 oct. 2017 06:23 Quand au temps d'exécution, il peut y avoir une fuite de temps lié au fait que mon HP prime était connecté par USB au 'Kit' sur mon portable ?
Bizarre !

Quel paramètre peut bien avoir un tel effet ?
J'ai déjà observé des comportements étranges du CAS qui se resolvent par un "restart", à la suite de quoi il faut recompiler les programmes CAS.
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

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

Message par Gilles59 »

zpalm a écrit : 26 oct. 2017 13:24
Gilles59 a écrit : 26 oct. 2017 11:46TEVAL ne fonctionne pas en CAS?
En mode CAS, essaye avec time au lieu de TEVAL.
Ca fonctionne avec 'time'. Ce coté bicéphale de la PRIME, Home d'un coté et CAS de l'autre avec de subtiles différences est le coté agaçant de cette superbe machine. Je trouve 0,52" (sans le IP du début dont je ne vois pas l'intérêt)
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
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 »

Très juste, l'IP ne sert ici à rien (il avait une utilité pour une version avec mnémonization mais je ne sais plus exactement pourquoi !)

Il y avait deux soucis sur ma Prime :
* un environnement CAS bien chargé (je n'avait pas fait de restart)
et un changement intempestif du format des nombres qui avait aussi fait disparaître la virgule dans l'éditeur de programme.

Je trouve donc maintenant moi aussi les résultats en 0.273_s en déclarant les variable m, f et t à l'aide de la commande LOCAL !
Image
Tout cela prouve que l'environnement CAS joue un rôle important dans la vitesse de l'évaluation des expressions !
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.
caloubugs
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 434
Enregistré le : 05 juin 2014 22:23
Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau

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

Message par caloubugs »

Xerxes a écrit : 16 mars 2017 23:45 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
Nice Xerxès ! (especially for the use of RST). But very very very slow (yes, even if it's the Ti62).
I propose this version, more powerful in time of realization (with bigger code, i know).

Code : Tout sélectionner

00 LBL F  //ok, but it's more comfortable - if not : erase lines 00 - 03 and replace line 19 by RST.
01 CM
02 STO 0
03 LBL 0
04 1
05 x<>t
06 RCL 0
07 x=t
08 GTO 3  // it can be R/S (and erase line 33 and after) : but recall RCL 1 and 2 manually (RCL 2 must be multiplied by 2)
09 LBL 1
10 C.t
11 2
12 ST/ 0
13 RCL 0
14 Frac
15 x>t
16 GTO 2
17 1
18 ST+ 1
19 GTO 0
20 LBL 2
21 3
22 ST* 0
23 2
24 ST+ 1
25 1/x
26 ST+0
27 RCL 2
28 x<>t
29 RCL 0
30 x>t
31 STO 2
32 GTO 1
33 LBL 3
34 RCL 1
35 R/S
36 2
37 ST* 2
38 RCL 2
39 R/S
It's a little faster (it's the Ti62 !), execution time : 308 seconds for the seed 27.
Juste type 27 and F.
40 lines for comfort, 29 in a lighter version with the same usage as yours (except RCL 2 must be multiplied by 2).
RetroGeek, mais pas que...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
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 »

caloubugs a écrit : 16 nov. 2017 10:45 I propose this version, more powerful in time of realization (with bigger code, i know).
A nice comparison of size vs speed optimizing.

Apropos speed, I was able to to make the PB-1000/2000C assembly version slightly faster:

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: ADB   $0,#1
     ADBL  §0,$8,L8
     SBBCL $16,$0,L8
     JR    NC,@00
     LDL   $16,$0,L8,J.@00
Execution speed on my PB-2000C Turbo with 2.0 instead of 0.91 MHz and 16 digits precision:

77031 -> 0.0455 sec (7692 steps/s)

8400511 -> 0.0888 sec (7714 steps/s)

I've also tried the speed with the necessary precision for an argument instead of 16 digits:

77031 with 8 digits -> 0.0262 sec (13359 steps/s)

8400511 with 12 digits -> 0.0726 sec (9435 steps/s)
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 »

I've no experience with the assembly language of the HP Saturn CPU, but after a closer look at the
somewhat unusual instruction set, I noticed an advantage for the Collatz calculation compared to the
CPUs used in the CASIO or SHARP pockets, that allows a compact and fast routine for 64 bit binaries.
I hope it's bug free, because it's untested. The necessary runtimes are calculated for the HP-71B:

Code : Tout sélectionner

      B=0 W
      D=0 W
      C=0 W
      LC 1
      R0=C
LBL00 ?ABIT=0 0
      GOYES LBL01
      D=D+1 A
      C=A W
      A=A+A W
      A=A+1 WP
      A=A+C W
      C=R0
      ?A<=B W
      GOYES LBL01
      B=A W
LBL01 D=D+1 A
      ASRB
      ?A>C W
      GOYES LBL00
      RTN

Input: N in register A

Output: steps in register D and maximum in B
77031 needs 33977 cycles or 0.0531 sec (6593 steps/s)

8400511 needs 66527 cycles or 0.104 sec (6590 steps/s)

This is pretty fast for 640 kHz and a precision of 64 bit. Using BCDs would be significantly slower,
because dividing by 2 means multiplying by 5 and dividing by 10 in assembly, what I've done in the
PB-1000/2000C version, to have a size optimized code. The 64 bit binary version on the PB-1000 is
around 50% faster but much longer.
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 »

Xerxes a écrit : 28 nov. 2017 14:02This is pretty fast for 640 kHz and a precision of 64 bit.
I've checked the service manual of the 71B for more details about the CPU clock speed. If I'm not mistaken, the frequency
of 640 kHz refers to the internal machine cycle, that consists of 4 clock cycles. So if we want to compare different CPUs,
it's better to use the clock cycles and not the machine cycles, because some CPUs have varying machine cycle length.
The correct frequency of the 71B should be 2.4-2.6 MHz normally, that gives a machine cycle speed of 600-650 kHz.


Some examples of the needed clock cycles for one machine cycle:

Zilog Z80 3-6

HP Saturn 4

CASIO HD61700 2-3 (PB-1000)

SHARP SC61860 3 (PC-1360)

SHARP SC62015 3 (PC-E500)


A comparison of the BCD performance using the execution time of a 16 digit addition command:

SHARP SC61860 93 cycles @ 768 kHz = 8258/s

CASIO HD61700 47 cycles @ 910 kHz = 19362/s

HP Saturn 82 cycles @ 2.5 MHz = 30488/s

SHARP SC62015 63 cycles @ 2.3 MHz = 36508/s
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5226
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

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

Message par bernouilli92 »

There is a mistake in the code for hp71.
The line
A=A+1 WP
should be
A=A+1 W
HP, Casio, Sharp, Psion, quelques TI et divers autres
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 »

Merci for your attention. It's a small optimization, that I've also used in the PB-1000/2000C code. It works, because the
content of register A is always even at that point, so it's only necessary to increment bit 0 or set it to 1. Therefore I've
rearranged the calculation of 3n+1 from n+n+n+1 to n+n+1+n.
Répondre

Retourner vers « Tous les Pockets »