Primzahl Prüfung Miller-Rabin Test

[NicknameFJ]

@Helle: Meine Assembler - Kenntnisse sind doch schon ziemlich eingerostet daher bin ich gleich auf BigInt umgestiegen. Aber für Deine Variante

aus Wikipedia:

Wenn die Zahl n klein ist, ist es nicht notwendig, alle a < 2(ln n)2 zu testen, da bekannt ist, dass eine viel kleinere Anzahl ausreichend ist. Beispielsweise haben Pomerance, Selfridge und Wagstaff sowie Jaeschke folgendes verifiziert:

Wenn n < 1.373.653, genügt es, a = 2 und 3 zu testen,
wenn n < 9.080.191, genügt es, a = 31 und 73 zu testen,
wenn n < 4.759.123.141, genügt es, a = 2, 7, und 61 zu testen,
wenn n < 2.152.302.898.747, genügt es, a = 2, 3, 5, 7, und 11 zu testen,
wenn n < 3.474.749.660.383, genügt es, a = 2, 3, 5, 7, 11, und 13 zu testen,
wenn n < 341.550.071.728.321, genügt es, a = 2, 3, 5, 7, 11, 13, und 17 zu testen.
wenn n < 3.825.123.056.546.413.051, genügt es, a = 2, 3, 5, 7, 11, 13, 17, 19, und 23 zu testen.
wenn n < 318.665.857.834.031.151.167.461, genügt es, a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, und 37 zu testen.

Dabei dürfen nur solche n getestet werden, die größer sind als das jeweils größte angegebene a.

Da die angegebene Zahl 318.665.857.834.031.151.167.461 größer ist als die größte positive QUAD und die größste zu prüfende Zahl ja in eine positive QUAD passen muss, kann man den Algo mit obigen Angaben auch recht einfach in einen deterministischen ändern und wirklich sicher sein dass bei Rückgabe #True die Zahl auch eine Primzahl ist.

Wenn ich die Tage mal Zeit finde baue ich die Procedure vlt. um sodass auch Zahlen größer als QUAD getestet werden können. Dann aber wieder mit BigInt auch wenn es deutlich langsamer ist als die Variante von Helle. Oder einer von Euch kommt mir da zuvor

[Dextro]

Als stiller Mitleser habe ich alle Beiträge interessiert verfolgt und kann nur staunen was Ihr Profis imstande seid zu leisten. Zu diesem Thema habe ich heute zufällig einen Bericht über einen neuen WR gelesen, den ich Euch nicht vorenthalten möchte, wenn Ihr es noch nicht gelesen habt.

https://www.mersenne.org/primes/

Schöne Grüße
Dextro

[NicknameFJ]

Eine Variante die komplett mit BigInt arbeitet im ersten Post hinzugefügt. Dadurch können theoretisch beliebig große Zahlen getestet werden; vgl. Hinweise im ersten Post.

[STARGÅTE]

Hallo NicknameFJ und Helle,

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

Diese Codeversion läuft jedoch nur auf x64 und im ASM-backend!

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()

[NicknameFJ]

Hallo STARGÅTE,

cool. Danke für die Verbesserung.

NicknameFJ

[SMaag]

hier eine leicht optimierte Version! Knapp 10% schneller, benötigt keine Array-Struct defintion!

Code: Alles auswählen

Procedure.i IsPrime_x64(Value.q)
; ============================================================================
; NAME: IsPrime_x64
; DESC: Attention! Only for ASM Backend and x64
; DESC: Performes a full deterministic Miller Rabin Test for signed 
; DESC: 64 Bit Intger.
; DESC: Because Miller Rabin use x², the caculation reaches
; DESC: 128Bit results. The CPU internal computes x64 MUL, DIV
; DESC: with 128Bit in RAX:RDX, so we can use 128Bit in ASM-Code.
; DESC: In normal PB-Code this isn't possible without a BigInt Lib.
; VAR(Value.q) : The Number to chrunch
; RET.i : #True: if Number is Prime
; ============================================================================
  
  ; based on Code from PB-Forum from STARGATE
  ; https://www.purebasic.fr/german/viewtopic.php?p=361719&hilit=Primzahlen#p361719
  
  ; 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
  
  ; hand made module is a littele faster on x64 than PB Modulo % (why???)
  Macro _MOD(Number, div)
    (Number-(Number/div)*div)
  EndMacro

  Protected ret = #True
  Protected *Try.Integer
  Protected.i Loops, Exponent, Base
  
	If Value < 0
 	  Value = -Value
 	EndIf 	
 	
 	#_BranchPrediction = #True ;#False/#True For 2 different versions
 	
  CompilerIf #_BranchPrediction
    ; ---------------------------------------------------------------------- 
    ; This Version with the seperate Modulo functions performs aprox. 
    ; 10% better. The Reason might be the BranchPrediction which 
    ; precalculates the ElseIf so the CPU don't have to do all the Modulos
    ; ---------------------------------------------------------------------- 

    If Value <=30                     ; Values up to 30 (2*3*5) , We handle direct    	 	   
      Select Value 
        Case 2, 3, 5, 7, 11, 13, 17, 19, 23, 29   ; all Primes <30
          ProcedureReturn #True
        Default
          ProcedureReturn #False   
      EndSelect 
      
    ; 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 Or Value%23=0 Or Value%29=0 
    ElseIf Value&1=0 Or _MOD(Value, 3) = 0 Or _MOD(Value, 5) = 0 Or _MOD(Value, 7) = 0
      ProcedureReturn #False
    ElseIf _MOD(Value, 11) = 0 Or _MOD(Value, 13) = 0 Or _MOD(Value, 17) = 0
      ProcedureReturn #False
    ElseIf _MOD(Value, 19) = 0 Or _MOD(Value, 23) = 0 Or _MOD(Value, 29) = 0
      ProcedureReturn #False
    EndIf
    
  CompilerElse
   ; ----------------------------------------------------------------------  
   ; This Version looks like to be the better and faster Code. 
   ; But it isn't. I tested the 2 Versions on new and older CPU 
   ; from 2011, 2016, 2020 and this version is always slower!
   ; ---------------------------------------------------------------------- 
    
    If Value <=30                     ; Values up to 30 (2*3*5) , We handle direct    	 	
      
      Select Value 
        Case 2, 3, 5, 7, 11, 13, 17, 19, 23, 29   ; all Primes <30
          ProcedureReturn #True
        Default
          ProcedureReturn #False   
      EndSelect 
      
    ElseIf (Value & 1) = 0            ; If Even(Value) 
      ProcedureReturn #False          ;   Not a Prime!
      
    Else                              ; from here on we have: Even Values > 30                                       
      Select (Value % 30)             ; Check Mod30 RestClasses: (Value Mod 5 =0) or (Value Mod 3 =0)
        Case 3,5,9,15,21,25,27        ; Prime not possible! Value IsNotElementOf Mod30 RestClass for PirmeCandidates
          ProcedureReturn #False       
        ; Case 1,7,11,13,17,19,23,29  ; Prime possible! Value IsElementOf Mod30 RestClass for PrimeCandidates [1,7,11,13, 17,19,23,29]      
      EndSelect    
    EndIf
    
  ; ----------------------------------------------------------------------   
  CompilerEndIf

	; with unrolling the loop we get a little faster code 	
	If Value < 2047
	  *Try = ?Lower_2047 
	 
	ElseIf Value <  1373653
	  *Try = ?Lower_1373653	  
	  
	ElseIf Value <  9080191
	  *Try = ?Lower_9080191
	  
	ElseIf Value <  25326001 
	  *Try = ?Lower_25326001
	  
	ElseIf Value <  3215031751
	  *Try = ?Lower_3215031751
	  
	ElseIf Value <  4759123141
	  *Try = ?Lower_4759123141	  
	  
	ElseIf Value <  1122004669633
	  *Try = ?Lower_1122004669633	  
	  
	ElseIf Value <  2152302898747
	  *Try = ?Lower_2152302898747	  
	  
	ElseIf Value <  3474749660383
	  *Try = ?Lower_3474749660383	  
	  
	ElseIf Value <  341550071728321
	  *Try = ?Lower_341550071728321	  
	  
	ElseIf Value <  3825123056546413051
	  *Try = ?Lower_3825123056546413051	  
	Else   
	  *Try = ?Lower_18446744073709551616  	  
	EndIf
	
  ; because for MillerRabin we need 128Bit, this is not possible in standard PB-Code

	; used Registers
  ;   RAX : operating Register MUL, DIV
  ;   RCX : Counter
  ;   RDX : operating Register MUL, DIV
  ;   R8  : Exponent
  ;   R9  : Value
  ;   R10 : -
	  	
	; Solve: 2^Loops * Exponent + 1 = Value
	!MOV   RAX, [p.v_Value]          ; RAX = Value
	!DEC   RAX                       ; RAX - 1
	!BSF   RCX, RAX                  ; Find LSB [0..63]
	!MOV   [p.v_Loops], RCX          ; Loops = LSB(Value)
	!SHR   RAX, cl                   ; RAX = (Value-1) >> LSB(Value)
	!MOV   [p.v_Exponent], RAX       ; Exponent = (Value-1) >> LSB(Value)
	
	; Witness loop
	!_WhileTry:
	!MOV RAX, QWORD [p.p_Try]         ; RAX = *Try
	!MOV RAX, [RAX]                   ; RAX = *Try\i
	!TEST RAX, RAX                    ; RAX == 0     
	!JZ _Return                       ; Jump _Retrun if 0 
  ;	While *Try\i
		
		;Base = *Try\i
		!MOV RAX, QWORD [p.p_Try]       ; RAX = *Try
		!MOV RAX, [RAX]                 ; RAX = *Try\i
    !MOV QWORD [p.v_Base],RAX       ; Base = *Try\i

		; RAX = Base^Exponent % Value
		!MOV  R8, [p.v_Exponent]        ; R8 = Exponent
		!MOV  R9, [p.v_Value]           ; R9 = Value
		!MOV  RAX, 1                    ; RAX = 1
		!BSR  RCX, R8                   ; RCX = MSB(Exponent)
		;Loop:
		!_InnerLoop:
			!MUL  RAX                     ; RAX = RAX * RAX
			!DIV  R9                      ; RAX:RDX = RAX:RDX / Value  
			!MOV  RAX, RDX                ; RAX = RAX % Value : Move Devision Remainder to RAX
			!BT   R8, RCX                 ; BitTest(Exponent, RCX), starts with RDX =  MSB(Exponent)
			!JNC @F
				!MUL  QWORD [p.v_Base]      ; RAX:RDX * Base
				!DIV  R9                    ; RAX:RDX / Value
				!MOV  RAX, RDX              ; RAX = Devision Remainder
			!@@:
			!DEC  RCX                     ; RCX-1 : Bitcounter - 1
		!JNS _InnerLoop
		
		; RAX = 1 or RAX = Value-1 ?
		!MOV  R8, R9                    ; R8 = Value
		!DEC  R8                        ; R8 = Value -1
		!CMP  RAX, 1                    ; If RAX = 1
		!JE  _Continue                  ;   Continue  
		!CMP  RAX, R8                   ; If RAX = Value -1
 		!JE  _Continue                  ;   Continue
	
		; Square-Mod-Loop: RAX = RAX^2 % Value  and check for  RAX = Value-1
		!MOV  RCX, [p.v_Loops]          ; RCX = Loops
		!@@:                            ; Repeat
			!MUL  RAX                     ; RAX * RAX
			!DIV  R9                      ; RAX:RDX / Value
			!MOV  RAX, rdx                ; RAX = Devsion Remainder
			!CMP  RAX, R8                 ; If RAX = VAlue -1
			!JE  _Continue                ;  Countinue
			!CMP  RAX, 1                  ; If RAX = 1
  		!JBE  _NoPrime                ; NoPrime	
  		!DEC  RCX                     ; RCX-1 : Bitcounter - 1
  	!JNZ @B                         ; Repeat If RCX<> 0
  		
	  ;	noprime:
		!_NoPrime:                      ; NoPrime
  		!XOR RAX, RAX                 ; RAX = 0
  		!MOV [p.v_ret], RAX           ; ret = 0
  		!JMP _Return                  ; Jump to Return
 		
		!_Continue:                     ; Continue
		;*Try + SizeOf(Integer)
  		!MOV    RAX, QWORD [p.p_Try]  ; RAX = *Try
      !ADD    RAX,8                 ; RAX + 8
      !MOV    QWORD [p.p_Try],RAX   ; *Try = *Try + 8   
    !JMP _WhileTry                  ; Repeat While Loop
  ;Wend
  !_Return:
  ProcedureReturn ret 
		
	; Witness bases
	DataSection 
		Lower_2047:                 : Data.q 2, 0
		Lower_1373653:              : Data.q 2, 3, 0
		Lower_9080191:              : Data.q 31, 73, 0
		Lower_25326001:             : Data.q 2, 3, 5, 0
		Lower_3215031751:           : Data.q 2, 3, 5, 7, 0
		Lower_4759123141:           : Data.q 2, 7, 61, 0
		Lower_1122004669633:        : Data.q 2, 13, 23, 1662803, 0
		Lower_2152302898747:        : Data.q 2, 3, 5, 7, 11, 0
		Lower_3474749660383:        : Data.q 2, 3, 5, 7, 11, 13, 0
		Lower_341550071728321:      : Data.q 2, 3, 5, 7, 11, 13, 17, 0
		Lower_3825123056546413051:  : Data.q 2, 3, 5, 7, 11, 13, 17, 19, 23, 0
		Lower_18446744073709551616: : Data.q 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 0
	EndDataSection
		
EndProcedure
  
OpenConsole()

Define N.i 
Define Count.i = 0  ; the first Prime is 2
Define Time.q = ElapsedMilliseconds()

For N = 0 To 10000000 ;Step 2
	If IsPrime_x64(N)
		Count + 1
	EndIf
Next
PrintN("Prime numbers: "+Str(Count))
PrintN("Evaluation time: "+Str(ElapsedMilliseconds()-Time))

Input()

[STARGÅTE]

Cool.

Kann die Verbesserung hier auf meiner Ryzen 9 3900X bestätigen, allerdings nicht ganz 10%.
Mein Code 580 ms, dein Code 540 ms.
Allerdings kann ich nicht bestätigen, dass (Number-(Number/div)*div) schneller ist als Number % div.
Bei mir kommt die selbe Zeit raus, manchmal ist % etwas schneller.
Eigenlicht nutzen % und / den selben ASM Befehl, nutzen nur halt einen anderen Ausgaberegister.
Die Ausführungszeit von DIV liegt jedoch im Bereich von 10-40 Taktzyklen, sodass die nachfolgende Multiplikation und Subtraktion mit je nur 1 Zyklus nicht ins Gewicht fällt.

Man könnte hier noch mal mit der FPU und extended precision (80 bit) eine Multiplikation mit dem Inversen der Primzahlen bis 30 probieren. Ich denke das gibt noch mal n gute Beschleunigung ohne die Genauigkeit zu verlieren.

[SMaag]

.
Allerdings kann ich nicht bestätigen, dass (Number-(Number/div)*div) schneller ist als Number % div.
Bei mir kommt die selbe Zeit raus, manchmal ist % etwas schneller.
Eigenlicht nutzen % und / den selben ASM Befehl, nutzen nur halt einen anderen Ausgaberegister.

mittlerweile hab ich etwas mehr Einblick in die Prozessorarchitekturen und die Code-Optimierungen wie Branch Prediction
und OutOfOrderExecution.
Ich hab das grundsätzlich nur 1x getestet. Das Problem dabei ist, dass es sich evtl. um Sondereffekte handelt, so dass genau
in meinem Kontext dadruch die Codeflussoptimierung verbessert wurde. Ähnliches ist mir schon öfter untergekommen, wenn
z.B. in einer Procedure vorher der Code verändert wird und die nachfolgende Procedure sich deutlich in der Ausführungszeit ändert.

(Number-(Number/div)*div) ist demnach nicht grundsätzlich schneller als MOD sondern nur unter bestimmten Umständen, die man
nich vorhersehen kann.

Dass die vielen Modulo Berechnungen schneller sind als eine einzelne mit einem Case auf das Ergebnis ist aber auch komisch!
Ich denke das liegt an der OutOfOrder Execution, wo das irgendwo bereits vor der eigentlichen Codeabarbeitung vorberechnet wird.

-------------------------------------------------------------------------------------------------------------------------------------------------------------

Was ich nochmal versuchen werde ist, die Case und If mit SIMD SSE Compare Befehlen parallel auszuführen.
Bei Werten kleiner 30 reicht ein Bytevergleich. Damit bringt man 16 Vergleiche gleichzeitig in ein XMM-Register
Es könnte aber sein, dass die dazu nötigen Shuffle Befehle das ganze auch langsamer machen!

(Update 29.09.2024: ich hab es probiert und es bringt nichts!)

Code: Alles auswählen

    
         If Num <=30                     ; Values up to 30 (2*3*5) , We handle direct    	 	
        
        Select Num 
          Case 2, 3, 5, 7, 11, 13, 17, 19, 23, 29   ; all Primes <30
            ProcedureReturn #True
          Default
            ProcedureReturn #False   
        EndSelect 

ähnlich könnte man mit der If Konstruktion umgehen
das sind 11 Vergleiche mit 64 Bit. Dafür benötigt man 5 XMM Vergleiche.
Wenn man 2 Register parallel für dei Vergleiche verwendet, könnte das
evtl. parallel ausgefürt werden und so auf die Zeit von 2+1 Vergleich
reduziert werden. Evtl. könnte man die ersten 4 Vergleiche auch als
32Bit ausführen, somit wäre das mit einem Befehl in XMM machbar!

Code: Alles auswählen

 	If Num < 2047
  	  *Try = ?Lower_2047 
  	 
  	ElseIf Num <  1373653
  	  *Try = ?Lower_1373653	  
  	  
  	ElseIf Num <  9080191
  	  *Try = ?Lower_9080191
  	  
  	ElseIf Num <  25326001 
  	  *Try = ?Lower_25326001
  	  
  	ElseIf Num <  3215031751
  	  *Try = ?Lower_3215031751
  	  
  	ElseIf Num <  4759123141
  	  *Try = ?Lower_4759123141	  
  	  
  	ElseIf Num <  1122004669633
  	  *Try = ?Lower_1122004669633	  
  	  
  	ElseIf Num <  2152302898747
  	  *Try = ?Lower_2152302898747	  
  	  
  	ElseIf Num <  3474749660383
  	  *Try = ?Lower_3474749660383	  
  	  
  	ElseIf Num <  341550071728321
  	  *Try = ?Lower_341550071728321	  
  	  
  	ElseIf Num <  3825123056546413051
  	  *Try = ?Lower_3825123056546413051	  
  	Else   
  	  *Try = ?Lower_18446744073709551616  	  
  	EndIf