MCODE - Prime Twin Finder - RFF (Request For Feedback)
Message #1 Posted by PeterP on 20 July 2008, 1:19 p.m.
Hi,
As is customary for me when trying to learn a new language, I try writing a prime-finder, prime-twin finder and testing goldbach's conjecture. We already have a very good prime-finder in MCODE (see SANDBOX or the original article from Jason DeLooze in PPCJ V11 N7 p30) so I decided to build a Prime-Twin finder as my second program in MCODE (the first one was the MCODE instruction timer see the discussion here a few weeks back)
It would be great to get some feedback and suggestions from the MCODE guru's around on how to improve the routine below as well as pointing out errors and mistakes I am sure I have made plenty off.
The listing can be copied into a .src file and can be directly assembled with a41, linked with l41 (just need a simple .lnk file which tells is where to link it to, I used page B) and then used with m41. This SDK41 from Warren is truly amazing!
Name: PTWIN
Purpose: Find the next prime twin numbers (p,p+2) greater than X.
Input: Starting number for the search in X
Output: p+2 in X, X in L, rest undisturbed. This allows for quick consecutive searches
Range: 1-1e10.
(well, actually the largest legal prime twin is 9,999,999,701 / 703 but following a note with regards to the cold start constant in the VASM from HPs programmer 'for now I leave well enough alone') I have not amended the range testing routine. It was however quite fun to use the program to find that number as I did not find a web-page which has such large primes. Using Warren's simulator PTWIN finds those high prime-twins within a couple of minutes actually...)
Name:FFACT
Purpose: Find the smallest prime factor of the number in X. PTWIN uses FFACT to test for prime-number.
Input: Number in X, 1<=X<1e10
Output: Stack copied (Z->T,Y->Z,X->Y, X-L), X has smallest prime factor.
One question for example is with regards to using a main-frame entry-point for copying the stack upwards. It would seem that such a entry-point must exist but I did not find a reference in either Ken's book nor the HEPAX manual.
Any and all comments would be much appreciated.
Thanks!
Peter
* PPPRIM.SRC
* Assembled by A41
* Sun Jul 20 13:20:54 2008
;***************** Start of PPPRIM rom ****************
.TITLE "PPPRIM"
.JDA
.EQU [PCTOC] 00D7
;**********************************
;* FAT for PPPRIM ROM *
;**********************************
0000 001 XROM 1 ;XROM number
0001 003 FCNS 3 ;Header + 1 function
0002 000088 DEFR4K [Header] 0088 ;first executable of header
0004 00008E DEFR4K [FFACT] 008E
0006 001028 DEFR4K [PTWIN] 0128
0008 000 NOP ;FAT termination
0009 000 NOP ;FAT termination
;***********************************
.FILLTO 0081
;******** Start of Code ************
;**** Header
.NAME "PPPRIM"
*0082 08D #08D ; "M"
*0083 009 #009 ; "I"
*0084 012 #012 ; "R"
*0085 010 #010 ; "P"
*0086 010 #010 ; "P"
*0087 010 #010 ; "P"
0088 3E0 [Header] RTN
;*********************************************************************
;FFACT is the PRIM function adapted for PTWIN.
;Gives First Factor which is the number itself if prime
; [FFACT] entry point does full check of range, div by 2 etc - Flag 5 is set!
; [PPRIM] entry point for PTWIN does no check of range and no div by 2
.NAME "FFACT"
*0089 094 #094 ; "T"
*008A 003 #003 ; "C"
*008B 001 #001 ; "A"
*008C 006 #006 ; "F"
*008D 006 #006 ; "F"
008E 078 [FFACT] READ 1(z)
008F 028 WRIT 0(T)
0090 0B8 READ 2(y)
0091 068 WRIT 1(z)
0092 0F8 READ 3(x)
0093 0A8 WRIT 2(y)
0094 128 WRIT 4(L)
;---------------------- Make sure starting point is less than 1e10
0095 2A0 SETDEC
0096 2FE ?C#0 MS
0097 033 JNC +6 009D
0098 23E C=C+1 MS
0099 389052 (adatp) ?NCGO [ERRAD] 14E2
009B 0B50A2 (derrp) ?NCGO [ERRDE] 282D
009D 2EE ?C#0 ALL
009E 3EB JNC (derrp) -3 009B
009F 2F6 ?C#0 XS
00A0 3DF JC (derrp) -5 009B
00A1 31C (cklpp) R= 1
00A2 2E2 ?C#0 @R
00A3 3C7 JC (derrp) -8 009B
00A4 10E A=C ALL
00A5 3EE (shflpp) LSHFA ALL
00A6 386 RSHFA S&X
00A7 35A ?A#0 M
00A8 023 JNC [Chk1] +4 00AC
00A9 1A6 A=A-1 S&X
00AA 3BF JC (cklpp) -9 00A1
00AB 3D3 JNC (shflpp) -6 00A5
;---------------------- Check if it is 1
00AC 0F8 [Chk1] READ 3(x)
00AD 0AE A<>C ALL
00AE 04E C=0 ALL
00AF 35C R= 12
00B0 050 LD@R 1
00B1 36E ?A#C ALL
00B2 07B JNC [ExitP] +15 00C1
;---------------------- Check division by 2
00B3 0BA [Chk2] A<>C M ;A has number, now C has Mant, and A Exp
00B4 2FC (shlp2) RCR 13 ;de facto a LSHF C
00B5 1A6 A=A-1 S&X
00B6 3F3 JNC (shlp2) -2 00B4
00B7 2FC RCR 13 ;first digit was moved to R=13 and now to C[0]
00B8 3D8 C<>ST ;move it into ST
00B9 04E C=0 ALL ;Set up correct exit if divisible by 2
00BA 35C R= 12 ;by storing 2 in B
00BB 090 LD@R 2
00BC 0EE B<>C ALL
00BD 088 SETF 5 ;Force setting of flag 5 - we are in Prime only mode
00BE 38C ?FSET 0 ;if the first flag not set, we have even number
00BF 02B JNC [ExitNP] +5 00C4
00C0 053 JNC [PPRIM] +10 00CA ;with Flag 5 set
;---------------------------------------- Exit Functions
00C1 04E [ExitP] C=0 ALL ;we have a prime; C=0
00C2 260 SETHEX ;to save jump distance in PTWIN loop
00C3 3E0 RTN
00C4 0EE [ExitNP] C<>B ALL ;we don't have a prime. C has the first divisor from B
00C5 260 SETHEX ;to save jump distance in PTWIN loop
00C6 08C ?FSET 5 ;are we in prime only mode?
00C7 3A0 ?NCRTN ;no, just return
00C8 0E8 WRIT 3(x) ;yes, write it into X reg and then return
00C9 3E0 RTN
;---------------------- Start of PRIME test for PTWIN
00CA 0F8 [PPRIM] READ 3(X)
00CB 2A0 SETDEC
00CC 2F9060 [SQREP] ?NCXQ [SQR10] 18BE ;get SQR(x)
00CE 03C RCR 3 ;move S&X into front
00CF 070 N=C ;save SQR in N
00D0 1A0 A=B=C=0
00D1 25C R= 9 ;Load Divisor Pattern
00D2 190 LD@R 6
00D3 090 LD@R 2
00D4 190 LD@R 6
00D5 110 LD@R 4
00D6 090 LD@R 2
00D7 110 LD@R 4
00D8 090 LD@R 2
00D9 110 LD@R 4
00DA 090 LD@R 2
00DB 090 LD@R 2
00DC 33C RCR 1
00DD 158 M=C ;Store into N
00DE 0F8 READ 3(x)
00DF 0AE A<>C ALL ;Store X in A
00E0 35C R= 12
00E1 0D0 LD@R 3
00E2 0EE C<>B ALL ;Store 3 (first divisor) in B
00E3 35C R= 12
00E4 04E [ploop] C=0 ALL
00E5 186 A=A-B S&X ;move S&X into C to keep track of
00E6 0E6 C<>B S&X
00E7 1BC RCR 11
00E8 0A6 A<>C S&X
00E9 18E (sub) A=A-B ALL ;subtract divisor in B repeatedly
00EA 3FB JNC (sub) -1 00E9
00EB 12E A=A+B ALL ;deal with underflow
00EC 3EE LSHFA ALL
00ED 266 C=C-1 S&X
00EE 3DB JNC (sub) -5 00E9 ;rinse and repeat
00EF 03C RCR 3
00F0 0E6 C<>B S&X
00F1 34E ?A#0 ALL ;if A=0 then it is not prime
00F2 293 JNC [ExitNP] -46 00C4
00F3 198 C=M ;otherwise, get pattern from M for next divisor
00F4 33C RCR 1
00F5 2E2 ?C#0 @R ;if 0, wrap around
00F6 017 JC (bis0) +2 00F8
00F7 17C RCR 6 ;wraparound
00F8 00E (bis0) A=0 ALL
00F9 102 A=C @R ;get next number to calc next divisor
00FA 12E A=A+B ALL ;calc next divisor
00FB 35E ?A#0 MS ;overflow?
00FC 033 JNC (noovfl) +6 0102
00FD 3E6 LSHFA S&X ;deal with overflow
00FE 38E RSHFA ALL
00FF 166 A=A+1 S&X
0100 3D4 R=R-1
0101 33C RCR 1
0102 158 (noovfl) M=C
0103 08E B=A ALL ;move new divisor into B
0104 0B0 C=N ;now get SQR
0105 0AE A<>C ALL
0106 03C RCR 3
0107 30E ?A<C ALL ;see if we are still <SQR
0108 027 JC [ExitP2] +4 010C ;no, we have a Prime
0109 0F8 READ 3(X) ;otherwise, rinse and repeat
010A 10E A=C ALL
010B 2CB JNC [ploop] -39 00E4
;---------------------------------------- Exit Function again as other one is too far away
010C 04E [ExitP2] C=0 ALL ;we have a prime; C=0
010D 260 SETHEX ;to save jump distance in main loop..
010E 3E0 RTN
;============== The End ========================================================================
010F 000 NOP
0110 000 NOP
0111 000 NOP
0112 000 NOP
0113 000 NOP
0114 000 NOP
0115 000 NOP
0116 000 NOP
0117 000 NOP
0118 000 NOP
0119 000 NOP
011A 000 NOP
011B 000 NOP
011C 000 NOP
011D 000 NOP
011E 000 NOP
011F 000 NOP
0120 000 NOP
0121 000 NOP
0122 000 NOP
;*********************************************************************
;Prime Twin Function
;Given a startung number nr>=10 and n<1e10 it gives the next prime-twins (p,p+2)
;the function places p+2 in x so that it can be rerun immediately for the next pai
;the largest ptwin that it can calculate is (9,999,999,701,9,999,999,703)
;so to be perfect the test for the starting point should be adjusted accordingly...
;starting numbers <10 all give (11,13) as the first pair
.NAME "PTWIN"
*0123 08E #08E ; "N"
*0124 009 #009 ; "I"
*0125 017 #017 ; "W"
*0126 014 #014 ; "T"
*0127 010 #010 ; "P"
0128 2A0 [PTWIN] SETDEC
;---------------------- Make sure starting point is less than 1e10
0129 0F8 READ 3(x)
012A 128 WRIT 4(L)
012B 2FE ?C#0 MS
012C 033 JNC +6 0132
012D 23E C=C+1 MS
012E 389052 (adat) ?NCGO [ERRAD] 14E2
0130 0B50A2 (derr) ?NCGO [ERRDE] 282D
0132 2EE ?C#0 ALL
0133 3EB JNC (derr) -3 0130
0134 2F6 ?C#0 XS
0135 3DF JC (derr) -5 0130
0136 31C (cklp) R= 1
0137 2E2 ?C#0 @R
0138 3C7 JC (derr) -8 0130
0139 10E A=C ALL
013A 3EE (shflp) LSHFA ALL
013B 386 RSHFA S&X
013C 35A ?A#0 M
013D 023 JNC (go) +4 0141
013E 1A6 A=A-1 S&X
013F 3BF JC (cklp) -9 0136
0140 3D3 JNC (shflp) -6 013A
;---------------------- Calc Base number as #-(#Mod30 +1), Min Startnumber is 29
0141 1A0 (go) A=B=C=0 ;clean slate
0142 0F8 READ 3(x) ;Calc #Mod30 and store #-#MOD30-1 in x as new base number
0143 128 WRIT 4(L) ;put it in LastX
0144 0AE A<>C ALL ;save it into A
0145 1A6 A=A-1 S&X ;chec if it is at least >=10
0146 14F JC [MinST] +41 016F ;Goto MinStart = 11
0147 166 A=A+1 S&X
0148 35C R= 12
0149 0D0 LD@R 3 ;Load 30
014A 226 C=C+1 S&X
014B 070 N=C
014C 171064 ?NCXQ [MOD10] 195C ;C=AModC = #Mod30
014E 070 N=C ;save #Mod30 into N
014F 0AE A<>C ALL ;prep for MF [AddOne]
0150 08E B=A ALL
0151 001060 ?NCXQ [ADDONE] 1800 ; disturbs M
0153 2BE C=-C-1 MS
0154 0AE A<>C ALL ;A=-(#Mod30+1)
0155 0F8 READ 3(x)
0156 0AE A<>C ALL ;C=-(#Mod30+1), A=#
0157 01D060 ?NCXQ [AD2_10] 1807 ;C=A+C; disturbs M
0159 0E8 WRIT 3(x) ;this is our base # BN
;------------------------ Calc actual start number which is BN + 12, 18 or 20
015A 0B0 [CASN] C=N ;now lets find out where to actually start looking for twins
015B 266 C=C-1 S&X ;if <=10 then we start at BN + 12
015C 12F JC (Ad12) +37 0181
015D 35C R= 12
015E 262 C=C-1 @R ;it could be 10 or 11
015F 2FA ?C#0 M
0160 10B JNC (Ad12) +33 0181 ;it was 10
0161 2E2 ?C#0 @R ;only true if >=20
0162 0A7 JC (Ad30) +20 0176
0163 3D4 R=R-1
0164 262 C=C-1 @R ;was it 11?
0165 2FA ?C#0 M
0166 0DB JNC (Ad12) +27 0181 ;it was 11 indeed
0167 2FC RCR 13 ;as S&X= 0, this is de facto a LSHF C
0168 0AE A<>C ALL
0169 04E C=0 ALL
016A 35C R= 12;
016B 1D0 LD@R 7 ;<(11+7=18)?
016C 1DA A=A-C M
016D 077 JC (Ad18) +14 017B ;otherwise it is Ad30
016E 043 JNC (Ad30) +8 0176 ;Add 30
;---------------------- Min Startnumber is 11
016F 35C [MinST] R= 12
0170 050 LD@R 1
0171 050 LD@R 1
0172 226 C=C+1 S&X
0173 0E8 WRIT 3(x)
0174 308 SETF 1 ;we want to start at [FST]
0175 0F3 JNC [Exit] +30 0193
;---------------------- Ad 12, 18 or 30 to Startnumber
0176 008 (Ad30) SETF 3 ;we want to start at [TRD]
0177 04E C=0 ALL ;Add 30 to BN
0178 35C R= 12
0179 0D0 LD@R 3
017A 063 JNC [CSN] +12 0186 ;Calc Start Number
017B 208 (Ad18) SETF 2 ;we want to start at [SND]
017C 04E C=0 ALL
017D 35C R= 12
017E 050 LD@R 1
017F 210 LD@R 8
0180 033 JNC [CSN] +6 0186 ;Calc Start Number
0181 308 (Ad12) SETF 1 ;we want to start at [FST]
0182 04E C=0 ALL
0183 35C R= 12
0184 050 LD@R 1
0185 090 LD@R 2
0186 226 [CSN] C=C+1 S&X ;Calc Start Number
0187 0AE A<>C ALL
0188 0F8 READ 3(x) ;BaseNumber BN
0189 01D060 ?NCXQ [AD2_10] 1807 ;StartNumber = BN + addon
018B 0E8 WRIT 3(x)
018C 260 SETHEX ;?NCXQREL needs HEX mode
018D 30C ?FSET 1 ;we want to start at FST - Start = BN + 12
018E 13F JC [FST] +39 01B5
018F 20C ?FSET 2 ;we want to start at SND - Start = BN + 12+6 = BN+18
0190 177 JC [SND] +46 01BE
0191 00C ?FSET 3 ;we want to start at TRD - Start = BN + 12+6+12 = BN+30
0192 1A7 JC [TRD] +52 01C6
0193 0C3 [Exit] JNC [START] +24 01AB
;-------------------------------------- End of Finding Starting Number ---------------------------------------
;----------------------------- We Found a PTWIN, placed here to make jump-distances <64
0194 1B0 [FPT] POPADR ;we found a PTWIN it is in X
0195 04E C=0 ALL
0196 358 ST=C
0197 3E0 RTN
;----------------------------- Check if Prime +2 is also Prime - placed here so that JC can get to it within 64 words
0198 2A0 [C+2] SETDEC
0199 0F8 READ 3(x)
019A 268 WRIT 9(Q)
019B 0AE A<>C ALL
019C 04E C=0 ALL
019D 35C R= 12
019E 090 LD@R 2
019F 01D060 ?NCXQ [AD2_10] 1807
01A1 0E8 WRIT 3(x)
01A2 260 SETHEX
01A3 37903C0CA ?NCXQREL [PPRIM] 00CA
01A6 2EE ?C#0 ALL ;Did we find a prime number?
01A7 36B JNC [FPT] -19 0194 ;Yes, exit the program
01A8 278 READ 9(Q) ;No, return to main loop
01A9 0E8 WRIT 3(x)
01AA 3E0 RTN
;-------------------------------------------------------------------------------------------------------------------------
;-------------------------------------- Start of PTWIN Searching Loop ------------------------------------------
01AB 260 [START] SETHEX
01AC 37903C0CA ?NCXQREL [PPRIM] 00CA ;PRIM finishes in HEX mode
01AF 2EE ?C#0 ALL ;Did we find a prime number?
01B0 37903C198 ?NCXQREL [C+2] 0198 ;Yes, so also check #+2
01B3 308 SETF 1 ;No, lets move on to next. Let [+12] we are [FST]
01B4 0D3 JNC [N+12] +26 01CE ;Add 12 to current number in X
01B5 304 [FST] CLRF 1
01B6 37903C0CA ?NCXQREL [PPRIM] 00CA
01B9 2EE ?C#0 ALL ;Did we find a prime number?
01BA 37903C198 ?NCXQREL [C+2] 0198 ;Yes, so also check #+2
01BD 14B JNC [N+6] +41 01E6 ;No, lets move to next
01BE 37903C0CA [SND] ?NCXQREL [PPRIM] 00CA
01C1 2EE ?C#0 ALL ;Did we find a prime number?
01C2 37903C198 ?NCXQREL [C+2] 0198 ;Yes, so also check #+2
01C5 04B JNC [N+12] +9 01CE ;No, lets move to next
01C6 37903C0CA [TRD] ?NCXQREL [PPRIM] 00CA
01C9 2EE ?C#0 ALL ;Did we find a prime number?
01CA 37903C198 ?NCXQREL [C+2] 0198 ;Yes, so also check #+2
01CD 2F3 JNC [START] -34 01AB ;No, so lets keep looking
;------------------------------- End of PTWIN Searching Loop
;-------- Add 12 to X
01CE 2A0 [N+12] SETDEC
01CF 0F8 READ 3(x) ; Add 12 to current number in Reg x
01D0 01C R= 3
01D1 2E2 (sffd) ?C#0 @R
01D2 01F JC (ffd) +3 01D5
01D3 3DC R=R+1
01D4 3EB JNC (sffd) -3 01D1
01D5 3DC (ffd) R=R+1
01D6 0AE A<>C ALL
01D7 04E C=0 ALL
01D8 050 LD@R 1
01D9 090 LD@R 2
01DA 14E A=A+C ALL
01DB 35E ?A#0 MS
01DC 023 JNC (novfl) +4 01E0
01DD 166 A=A+1 S&X
01DE 3E6 LSHFA S&X
01DF 38E RSHFA ALL
01E0 0AE (novfl) A<>C ALL
01E1 0E8 WRIT 3(x)
01E2 260 SETHEX ;Set HEX mode for ?NCXQREL that comes in main loop
01E3 30C ?FSET 1 ;Did we come from First ?
01E4 28F JC [FST] -47 01B5 ;Yes
01E5 30B JNC [TRD] -31 01C6 ;No, it was the last one
;-------- Add 6 to X
01E6 2A0 [N+6] SETDEC
01E7 0F8 READ 3(x) ;Add 6 to current number in Reg x
01E8 01C R= 3
01E9 2E2 (sffd6) ?C#0 @R
01EA 01F JC (ffd6) +3 01ED
01EB 3DC R=R+1
01EC 3EB JNC (sffd6) -3 01E9
01ED 0AE (ffd6) A<>C ALL
01EE 04E C=0 ALL
01EF 190 LD@R 6
01F0 14E A=A+C ALL
01F1 35E ?A#0 MS
01F2 023 JNC (novfl6) +4 01F6
01F3 166 A=A+1 S&X
01F4 3E6 LSHFA S&X
01F5 38E RSHFA ALL
01F6 0AE (novfl6) A<>C ALL
01F7 0E8 WRIT 3(x)
01F8 260 SETHEX ;Set HEX mode for ?NCXQREL that comes in main loop
01F9 22B JNC [SND] -59 01BE
;==============================================================
*
* GLOBAL SYMBOLS
* SYMBOL VALUE TYPE REFERENCES
* [C+2] 0198 REL 01B0 01BA 01C2 01CA
* [CASN] 015A REL
* [CSN] 0186 REL 017A 0180
* [Chk1] 00AC REL 00A8
* [Chk2] 00B3 REL
* [ExitNP] 00C4 REL 00BF 00F2
* [ExitP2] 010C REL 0108
* [ExitP] 00C1 REL 00B2
* [Exit] 0193 REL 0175
* [FFACT] 008E REL 0004
* [FPT] 0194 REL 01A7
* [FST] 01B5 REL 018E 01E4
* [Header] 0088 REL 0002
* [MinST] 016F REL 0146
* [N+12] 01CE REL 01B4 01C5
* [N+6] 01E6 REL 01BD
* [PCTOC] 00D7 ABS
* [PPRIM] 00CA REL 00C0 01A3 01AC 01B6 01BE 01C6
* [PTWIN] 0128 REL 0006
* [SND] 01BE REL 0190 01F9
* [SQREP] 00CC REL
* [START] 01AB REL 0193 01CD
* [TRD] 01C6 REL 0192 01E5
* [ploop] 00E4 REL 010B
*
* LOCAL SYMBOLS
* SYMBOL VALUE TYPE REFERENCES
* (Ad12) 0181 REL 015C 0160 0166
* (Ad18) 017B REL 016D
* (Ad30) 0176 REL 0162 016E
* (adat) 012E REL
* (adatp) 0099 REL
* (bis0) 00F8 REL 00F6
* (cklp) 0136 REL 013F
* (cklpp) 00A1 REL 00AA
* (derr) 0130 REL 0133 0135 0138
* (derrp) 009B REL 009E 00A0 00A3
* (ffd) 01D5 REL 01D2
* (ffd6) 01ED REL 01EA
* (go) 0141 REL 013D
* (noovfl) 0102 REL 00FC
* (novfl) 01E0 REL 01DC
* (novfl6) 01F6 REL 01F2
* (sffd) 01D1 REL 01D4
* (sffd6) 01E9 REL 01EC
* (shflp) 013A REL 0140
* (shflpp) 00A5 REL 00AB
* (shlp2) 00B4 REL 00B6
* (sub) 00E9 REL 00EA 00EE
*
* EXTERNAL REFERENCES
* SYMBOL REFERENCED AT
*
* MAINFRAME REFERENCES
* SYMBOL VALUE REFERENCES
* [AD2_10] 1807 0157 0189 019F
* [ADDONE] 1800 0151
* [ERRAD] 14E2 0099 012E
* [ERRDE] 282D 009B 0130
* [MOD10] 195C 014C
* [SQR10] 18BE 00CC
*
* A41: 0 WARNINGS(S)
* A41: 0 ERROR(S)
* END
|
Go back to the main exhibit hall