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

[C.Ret]

Sur Hp prime, je trouve:

MPO53.syr2.png (9.08 Kio) Vu 14987 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

[Gilles59]

Sur Hp prime, je trouve:

Ce qui tend à prouver que ce n'est pas une overflow

En effet, même résultat en 0,58" dont 0,5" à se trainer à 6MHz ;D

[zpalm]

Sur Hp prime, je trouve:

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.

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

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

[zpalm]

TEVAL ne fonctionne pas en CAS?

En mode CAS, essaye avec time au lieu de TEVAL.

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]

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

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

Tout cela prouve que l'environnement CAS joue un rôle important dans la vitesse de l'évaluation des expressions !

[caloubugs]

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

[Xerxes]

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)

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

[Xerxes]

This 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

[bernouilli92]

There is a mistake in the code for hp71.
The line
A=A+1 WP
should be
A=A+1 W

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

[Marge]

Syracuse, la cité d'Archimède, méritait bien un peu d'archéologie.

Je viens de découvrir cette vidéo en français qui propose le calcul de la suite de Syracuse pour un Psion Organizer II (à 14 m 27 s environ).

Pour info, ce type propose d'autres programmes de maths pour d'autres machines, dont la Numworks.