[HP35s] Program for prime number (Wheel Sieve and Miller-Rabin)

[fred_76]

(02-14-2019 08:50 PM)Thomas Klemm Wrote:  Here's a program for the HP-42S using this idea:

Code:

00 { 120-Byte Prgm }
01▸LBL "PRIME?"
02 STO 09
03 1
04 STO 00
05 7
06 STO 01
07 11
08 STO 02
09 13
10 STO 03
11 17
12 STO 04
13 19
14 STO 05
15 23
16 STO 06
17 29
18 STO 07
19 30
20 STO 08
21 RCL 09
22 RCL 09
23 RCL 09
24 2
25 MOD
26 X<>Y
27 3
28 MOD
29 ×
30 X<>Y
31 5
32 MOD
33 ×
34▸LBL 00
35 X<>Y
36 RCL 01
37 MOD
38 ×
39 X<>Y
40 RCL 02
41 MOD
42 ×
43 X<>Y
44 RCL 03
45 MOD
46 ×
47 X<>Y
48 RCL 04
49 MOD
50 ×
51 X<>Y
52 RCL 05
53 MOD
54 ×
55 X<>Y
56 RCL 06
57 MOD
58 ×
59 X<>Y
60 RCL 07
61 MOD
62 ×
63 X=0?
64 RTN
65 CLX
66 RCL 07
67 X↑2
68 X>Y?
69 RTN
70 CLX
71 RCL 08
72 STO+ 00
73 STO+ 01
74 STO+ 02
75 STO+ 03
76 STO+ 04
77 STO+ 05
78 STO+ 06
79 STO+ 07
80 CLX
81 RCL 00
82 MOD
83 GTO 00
84 END

Translation should be straight forward for the HP-35s or pretty much any calculator that supports MOD and register arithmetics.
(...)
Cheers
Thomas

Version 8

I entered the program in the HP35s, it was straightforward.
The measured run times are still slower than V3 :

Run time
6 digits 999 983 = 13.4 s
7 digits 9 999 991 = 40,4 s

The difference between the two algorithms at each cycle are :

• V3 : stack ops = 16 | additions = 8 | multiplications = 0 | MOD = 8 | tests = 9
• V8 : stack ops = 9 | additions = 8 | multiplications = 7 | MOD = 8 | tests = 2
  

The 7 multiplications in V8 take longer to calculate than the additional 7 tests and stack operations in V3.

(02-14-2019 09:17 PM)Thomas Klemm Wrote:  You can also try numbered registers instead of variables. I could imagine that they are faster. But I could be completely wrong.

There is no "numbered" registers in the HP35S to my knowledge, just alpha registers and indirect registers.

I measured the time taken (1000 loops) to calculate the execution time of indirect vs direct registers. The unit op exec time is then :

• RCL (I) = 10 ms
• RCL I = 5 ms
  

We should better use direct registers to win time.