ich habe mal eure Codes als Vorlage für einen vollständig deterministischen Test für Primzahlen im gesamten Quad-Bereich (2^63-1) verwendet.
Zur Geschwindigkeitsoptimierung teste ich nebenbei vorher erst noch kleine Primzahlen bis 19 und nehme dann je nach Zahl ein bestimmtes Set an Witness Basen (Siehe Wiki). Damit konnte ich gegenüber Helles Version noch mal n Faktor 3 rausholen bei Zahlen zwischen 1 und 10^8
Code: Alles auswählen
CompilerIf #PB_Compiler_Processor <> #PB_Processor_x64 Or (Defined(PB_Compiler_Backend, #PB_Constant) And #PB_Compiler_Backend <> #PB_Backend_Asm)
CompilerError "Olny for ASM-backend and x64 processor"
CompilerEndIf
Structure IntegerArray
i.i[0]
EndStructure
Structure QuadArray
q.q[0]
EndStructure
Procedure.i IsPrime(Value.q)
; https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
; https://en.wikipedia.org/wiki/Exponentiation_by_squaring
; https://www.purebasic.fr/german/viewtopic.php?f=8&t=30523
; Thanks to NicknameFJ und Helle
Protected *Try.Integer, Loops.i, Exponent.q, Index.i, Base.q
Protected *Comparison.QuadArray = ?Lower
Protected *Label.IntegerArray = ?Label
Protected *SmallPrimes.IntegerArray = ?SmallPrimes
If Value < 0
Value = -Value
EndIf
; Testing small primes and divisibility using small primes
If Value < 20
ProcedureReturn *SmallPrimes\i[Value]
ElseIf Value & 1 = 0 Or Value % 3 = 0 Or Value % 5 = 0 Or Value % 7 = 0 Or
Value % 11 = 0 Or Value % 13 = 0 Or Value % 17 = 0 Or Value % 19 = 0
ProcedureReturn #False
EndIf
; Determine the required determenistic list for test bases
*Try = ?Lower_18446744073709551616
For Index = 0 To 10
If Value < *Comparison\q[Index]
*Try = *Label\i[Index]
Break
EndIf
Next
; Solve: 2^Loops * Exponent + 1 = Value
! MOV rax, [p.v_Value]
! DEC rax
! BSF rcx, rax
! MOV [p.v_Loops], rcx
! SHR rax, cl
! MOV [p.v_Exponent], rax
; Witness loop
While *Try\i
Base = *Try\i
; rax = Base^Exponent % Value
! MOV r8, [p.v_Exponent]
! MOV r9, [p.v_Value]
! MOV rax, 1
! BSR rcx, r8
Loop:
! MUL rax
! DIV r9
! MOV rax, rdx
! BT r8, rcx
! JNC @F
! MUL qword [p.v_Base]
! DIV r9
! MOV rax, rdx
!@@:
! DEC rcx
! JNS ll_isprime_loop
; rax = 1 or rax = Value-1 ?
! MOV r8, r9
! DEC r8
! CMP rax, 1
! JE ll_isprime_nexttry
! CMP rax, r8
! JE ll_isprime_nexttry
; Square-Mod-Loop: rax = rax^2 % Value and check for rax = Value-1
! MOV rcx, [p.v_Loops]
!@@:
! MUL rax
! DIV r9
! MOV rax, rdx
! CMP rax, r8
! JE ll_isprime_nexttry
! CMP rax, 1
! JBE ll_isprime_noprime
! DEC rcx
! JNZ @B
NoPrime:
ProcedureReturn #False
NextTry:
*Try + SizeOf(Integer)
Wend
ProcedureReturn #True
; IsPrime() for n = 0 to 19
DataSection
SmallPrimes:
Data.i #False, #False, #True, #True, #False, #True, #False, #True, #False, #False
Data.i #False, #True, #False, #True, #False, #False, #False, #True, #False, #True
EndDataSection
; Witness bases
DataSection
Lower_2047: : Data.i 2, 0
Lower_1373653: : Data.i 2, 3, 0
Lower_9080191: : Data.i 31, 73, 0
Lower_25326001: : Data.i 2, 3, 5, 0
Lower_3215031751: : Data.i 2, 3, 5, 7, 0
Lower_4759123141: : Data.i 2, 7, 61, 0
Lower_1122004669633: : Data.i 2, 13, 23, 1662803, 0
Lower_2152302898747: : Data.i 2, 3, 5, 7, 11, 0
Lower_3474749660383: : Data.i 2, 3, 5, 7, 11, 13, 0
Lower_341550071728321: : Data.i 2, 3, 5, 7, 11, 13, 17, 0
Lower_3825123056546413051: : Data.i 2, 3, 5, 7, 11, 13, 17, 19, 23, 0
Lower_18446744073709551616: : Data.i 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 0
EndDataSection
; Witness bases index
DataSection
Lower:
Data.q 2047, 1373653, 9080191, 25326001, 3215031751, 4759123141, 1122004669633
Data.q 2152302898747, 3474749660383, 341550071728321, 3825123056546413051
Label:
Data.i ?Lower_2047, ?Lower_1373653, ?Lower_9080191, ?Lower_25326001, ?Lower_3215031751
Data.i ?Lower_4759123141, ?Lower_1122004669633, ?Lower_2152302898747
Data.i ?Lower_3474749660383, ?Lower_341550071728321, ?Lower_3825123056546413051
EndDataSection
EndProcedure
OpenConsole()
Define N.i, Count.i
Define Time.q = ElapsedMilliseconds()
For N = 0 To 10000000
If IsPrime(N)
Count + 1
EndIf
Next
PrintN("Prime numbers: "+Str(Count))
PrintN("Evaluation time: "+Str(ElapsedMilliseconds()-Time))
Input()