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

[fred_76]

(thank you Thomas, it works !)

Here are the comparison of the versions of the program I tested so far. The version that is presented at the top of this thread is the version 3, i.e. the optimized one for "brute force".

Next step would be to implement the AKS, Miller-Rabin or SPRP, but those algorithms are quite difficult to program to my level...

Version 1
The principle was to use only the stack registers, i.e. no variable. The trial factors steps are such that the multiples of 2, 3 and 5 are discarded from the tests. These steps are 4,2,4,2,4,6,2,6 starting from 7.

The main loop is :

Code:

CLx
(trial factor step)
LAST X
+
RMDR
x=0?
GTO :is_not_prime

At the end of the cycle, there is a test to check if the trial factor is lower than the square root of the number to test. In fact, as the calculation of x² is faster than the calculation of √x, the comparison is made between the square of the trial factor and the number.

Code:

CLx
LAST X
x²
x>=y?
GTO :is_prime
GTO :loop_again

Run time
6 digits 999 983 0'18.42''

Version 2
The HP35S takes far more time to evaluate the constants than recalling them from a variable.

For example the following code :

Code:

1
+

takes about 2.2 more time than (1 is stored in variable I) :

Code:

RCL I
+

The 2nd version code is :

Code:

CLx
RCL (trial_factor_step)
LAST X
+
RMDR
x=0?
GTO :is_not_prime

Run time
6 digits 999 983 0'12.16''
1.5 faster than original version

Version 3
Another optimization is done. The HP35S can make some operations together with recalling/storing variables. And this is quite effective.

If 1 is stored in I, the following code

Code:

RCL I
+

takes about 1.9 more times than

Code:

RCL+ I

.

The 3rd version code is :

Code:

CLx
LAST X
RCL+ (trial_factor_step)
RMDR
x=0?
GTO :is_not_prime

A second optimization is done on the exit part. When a test is done, it runs faster when the test returns "true" than when it returns "false", and also when the condition is exclusive (< or >) than inclusive (<= or >=).

Code:

CLx
LAST X
x²
x<y?
GTO :loop_again
GTO :is_prime

Run time
6 digits 999 983 0m 9.8s (about 2x faster than V0)
7 digits 9 999 991 0m 28s
8 digits 99 999 989 1m 28s
9 digits 999 999 937 4m 36s
10 digits 9 999 999 967 14m 37s
11 digits 99 999 999 977 46m 26s
12 digits 999 999 999 989 2h 32m 18s

Version 4
Instead of calculating x² at each end of cycle, store √N in a variable and compare with the trial factor. The problem is that the stack is quite tricky to restore and those operations take slightly more time than the calculation of x², therefore it is not a good idea.

Run time
8 digits 99 999 989 1m 30s (2 s more than V3)

Version 5
Based on V3, after idea of Albert Chan, precalculate the max number of cycles to be made C = INT[(N-7)/30]+1 and use of DSE. The problem is that DSE takes more time than calculating x².

Run time
8 digits 99 999 989 1m 34s (6 s more than V3)

Version 6
Instead of duplicating the same lines of code for each trial factor step, call a subroutine.
But calling subroutines takes more time. It is good for the sake of the HP35s memory, but not time effective.

Run time
8 digits 99 999 989 1m 42s (14 s more than V3)

Version 7
Just for fun, store trial factor steps in indirect registers and call subroutines. This is definitely not time effective.

Run time
8 digits 99 999 989 3m 12s (2.2x slower than V3)