ught a DM42
Using Boubker’s primality test program (viewtopic.php?t=3073) as a base to explore the possibilities with the Free42 Extensions, I ended up with this program.
By the way, the thread briefly discusses a bug where the program, for instance, reports N=5 as NOT PRIME. This bug appears because this deterministic Milller-Rabin test does not work when a MR-base mod N = 0. The referenced Wikipedia article with the pseudo code fails to mention this.
My program works like a built-in conditional function; used in a program the next program line is skipped if test negative; executed from the keyboard it reports the test result with Yes/No. It alters no user flags or registers including the Alpha and Stack registers.
The test range is up to 1E17 to enjoy fast execution time (a couple of seconds on battery power regardless of number size in the range) and no need for code to handle overflow conditions. The biggest prime in the range is 99,999,999,999,999,997.
The program does not accept negative numbers and views the number 1 as neither prime nor composite in line with the common view among today’s mathematicians.
The two subroutines LBL20 (performs Miller-Rabin test for a MR-base) and LBL30 (calculates MR-base**D mod N with the fast Right-to-left binary method) might be somewhat hard to understand as they keep some variables in the stack instead of STO/RCLs. The rest of the program should be easy to understand.
The variables in stack are Result and D for LBL20 and Result and MR-base for LBL30.
The program uses the 4-level stack, but switches to the big stack to create a List of MR-bases, so “Dynamic Stack Extension” must be enabled in SETUP.
Code: Select all
00 { 192-Byte Prgm }
01▸LBL "PRM?"
02 FUNC 00
03 LSTO "N"
04 REAL?
05 SKIP
06 RTNERR 4
07 ENTER
08 IP
09 X≠Y?
10 RTNERR 4
11 1ᴇ17
12 X<Y?
13 RTNERR 2
14 R↓
15 NSTK
16 2
17 3
18 5
19 7
20 11
21 13
22 17
23 19
24 23
25 9
26 →LIST
27 4STK
28 LSTO "W"
29 X<>Y
30 POS
31 X≥0?
32 RTNYES
33 +
34 X≤0?
35 RTNERR 5
36▸LBL 08
37 2
38 ÷
39 IP
40 LASTX
41 X=Y?
42 GTO 08
43 STO+ ST X
44 LSTO "D"
45▸LBL 09
46 HEAD "W"
47 SKIP
48 RTNYES
49 XEQ 30
50 SIGN
51 RCL "D"
52 R↓
53 X≠Y?
54 XEQ 20
55 GTO 09
56 RTNNO
57▸LBL 20
58 +/-
59 RCL+ "N"
60 X=Y?
61 RTN
62 R↑
63 X=Y?
64 RTNNO
65 STO+ ST X
66 X<> ST Z
67 X↑2
68 RCL "N"
69 MOD
70 1
71 X=Y?
72 RTNNO
73 GTO 20
74▸LBL 30
75 RCL "D"
76 LSTO "D"
77 SIGN
78▸LBL 10
79 RCL "D"
80 IP
81 X=0?
82 RTN
83 2
84 STO÷ "D"
85 MOD
86 R↓
87 GTO IND ST T
88▸LBL 01
89 ×
90 RCL "N"
91 MOD
92▸LBL 00
93 X<>Y
94 X↑2
95 RCL "N"
96 MOD
97 X<>Y
98 GTO 10
99 END