PureBoard

Das deutsche PureBasic-Forum
https://www.purebasic.fr/german/

ggT->groesster geimensammer teiler

https://www.purebasic.fr/german/viewtopic.php?t=8581

Seite 2 von 3

Verfasst: 29.05.2006 14:12
von Froggerprogger
Ach jau, sorry, es gibt ja den euklidischen und den erweiterten euklidischen Algorithmus, die beiden habe ich zusammengeworfen.

Verfasst: 29.05.2006 14:28
von Karl
Ich habe noch einen (eventuell) kürzeren:

Code: Alles auswählen

Procedure.l GGT2(Zahl1.l, Zahl2.l)
  
  Protected temp.l
  
  If Zahl1 > 0 And Zahl2 > 0
    While (Zahl1 > 0)
      If Zahl1 > Zahl2
        temp = Zahl1
        Zahl1 = Zahl1 % Zahl2
        Zahl2 = temp
      Else
        ;Tauschen
        temp = Zahl1
        Zahl1 = Zahl2
        Zahl2 = temp
      EndIf
    Wend
  EndIf
  
  ProcedureReturn Zahl2
  
EndProcedure
Der ist auf jedenfall schneller als der einfache.

Gruß Karl

Verfasst: 29.05.2006 15:17
von remi_meier
Darf mich ja nicht so schnell geschlagen geben :)

Code: Alles auswählen

Procedure.l gcd(m.l, n.l) 
  Protected k.l = 0
  
  !MOV Eax, [p.v_m]
  !AND Eax, Eax
  !JGE @f
  !NEG Eax
  !@@:
  !MOV Ecx, [p.v_n]
  !AND Ecx, Ecx
  !JGE @f
  !NEG Ecx
  !@@:
  
  ; eax = m, ecx = n
  !@@:
  !MOV Edx, Eax
  !AND Edx, 1
  !JNZ @f
  !MOV Edx, Ecx
  !AND Edx, 1
  !JNZ @f ;>
    !SAR Eax, 1
    !SAR Ecx, 1
    !INC dword[p.v_k]
    !JMP @b
  !@@: ;<
  
  !MOV Edx, Ecx
  !AND Edx, 1
  !JNZ @f ;>
    !XCHG Eax, Ecx
  !@@: ;<
  
  ; eax = m, ecx = n
  !@@:
  !AND Eax, Eax
  !JZ @f ;>
    !.LOOP:
    !MOV Edx, Eax
    !AND Edx, 1
    !JNZ .endloop ;>
      !SAR Eax, 1
      !JMP .LOOP
    !.endloop: ;<
    
    !CMP Eax, Ecx
    !JNL .endif ;>
      !XCHG Eax, Ecx
    !.endif: ;<
    
    !SUB Eax, Ecx
  !JMP @b ;<
  !@@:
  
  !MOV Eax, Ecx
  !MOV Edx, 1
  !MOV Ecx, [p.v_k]
  !SAL Edx, cl
  !IMUL Eax, Edx
  
  ProcedureReturn 
EndProcedure
Ist zwar sehr unschön, also noch relativ unoptimal, da ich nur direkt PB-
Code übersetzt habe ohne gross zu überlegen. Wenns wieder jemand
unterbietet, setz ich mich nochmals ran :)
So siehts hier im Moment aus:
FindggT: 1329 gcd: 296 ggt: 360 ggtAsm: 328
@Karl, dein Code scheint immer noch zu langsam.

Der Algorithmus von mir ist übrigens von Wikipedia. Dabei steht, dass er
speziell für Computer optimiert ist (Binary-Shifting). Ich denke also, er
sollte einer der schnellsten sein.

greetz
Remi

Verfasst: 29.05.2006 17:06
von inc.
Karl hat geschrieben:Das möchte ich mal bestreiten. Dieser ist der ursprüngliche - deiner offenbar die Erweiterung (wegen O(n)-Laufzeit).
Beide sind euklidisch.
Der eine ist der Subtraktions-Algorithmus und der andere der Divisions(Modulo)-Algorithmus.

Verfasst: 29.05.2006 17:33
von inc.
ggt: 360 ggtAsm: 328
Was das Kaeru's ABSx() Tip bzgl. ausmaskieren des Voreichens via Binäroperator angeht ...
würde das bei dem schnellsten non-ASM code so aussehen?

Code: Alles auswählen

Procedure.l ggT(a.l, b.l) ; euclid
  Protected temp.l

  a & 7FFFFFFF 
  b & 7FFFFFFF
 
  While (b > 0)
      temp = b
       b    = a % b
       a    = temp
  Wend
  ProcedureReturn a
EndProcedure

Verfasst: 30.05.2006 00:50
von Froggerprogger
Das sind meine Ergebnisse hier. Noch ist bei mir also die handoptimierte Asm-Version des erweiterten Euklid der schnellste, auch schneller als remis version des shift-algos.

FindggT: 1422 gcd: 453 gcdAsm: 453 ggt: 391 ggtAsm: 343 GGT2: 625 GGT2B: 422

Das unterliegt natürlich Schwankungen, aber die Verhältnisse bleiben immer gleich.

Folgender Code (sorry, schon ganz schön sperrig)

Code: Alles auswählen

Procedure FindggT(a,b) 
  Protected m=a 
  Protected n=b 
  Protected s=1 
  Protected t=0 
  Protected u=0 
  Protected v=1 
  
  While n>0 
    q=Round(m/n,0) ;Der Quotient wird abgerundet 
    r=m-q*n 
    m=n 
    n=r 
    tmp=u 
    u=s-q*u 
    s=tmp 
    tmp=v 
    v=t-q*v 
    t=tmp 
  Wend 
  
  ProcedureReturn m 
EndProcedure 

Procedure.l gcd(m.l, n.l) 
  Protected k.l = 0 
  
  If n < 0 : n * (-1) : EndIf 
  If m < 0 : m * (-1) : EndIf 
  
  While (m % 2 = 0 And n % 2 = 0) 
    m >> 1 
    n >> 1 
    k + 1 
  Wend 
  If n % 2 = 0 
    Swap m, n 
  EndIf 
  
  While m <> 0 
    While (m % 2 = 0) 
      m >> 1 
    Wend 
    
    If m < n 
      Swap m, n 
    EndIf 
    m - n 
  Wend 
  
  ProcedureReturn n * (1 << k) 
EndProcedure 

Procedure.l gcdAsm(m.l, n.l) 
  Protected k.l = 0 
  
  !MOV Eax, [p.v_m] 
  !AND Eax, Eax 
  !JGE @f 
  !NEG Eax 
  !@@: 
  !MOV Ecx, [p.v_n] 
  !AND Ecx, Ecx 
  !JGE @f 
  !NEG Ecx 
  !@@: 
  
  ; eax = m, ecx = n 
  !@@: 
  !MOV Edx, Eax 
  !AND Edx, 1 
  !JNZ @f 
  !MOV Edx, Ecx 
  !AND Edx, 1 
  !JNZ @f ;> 
    !SAR Eax, 1 
    !SAR Ecx, 1 
    !INC dword[p.v_k] 
    !JMP @b 
  !@@: ;< 
  
  !MOV Edx, Ecx 
  !AND Edx, 1 
  !JNZ @f ;> 
    !XCHG Eax, Ecx 
  !@@: ;< 
  
  ; eax = m, ecx = n 
  !@@: 
  !AND Eax, Eax 
  !JZ @f ;> 
    !.LOOP: 
    !MOV Edx, Eax 
    !AND Edx, 1 
    !JNZ .endloop ;> 
      !SAR Eax, 1 
      !JMP .LOOP 
    !.endloop: ;< 
    
    !CMP Eax, Ecx 
    !JNL .endif ;> 
      !XCHG Eax, Ecx 
    !.endif: ;< 
    
    !SUB Eax, Ecx 
  !JMP @b ;< 
  !@@: 
  
  !MOV Eax, Ecx 
  !MOV Edx, 1 
  !MOV Ecx, [p.v_k] 
  !SAL Edx, cl 
  !IMUL Eax, Edx 
  
  ProcedureReturn 
EndProcedure

Procedure.l ggT(a.l, b.l) ; euclid
  Protected temp.l
  If a < 0
    a = -a
  EndIf
  If b < 0
    b = -b
  EndIf
  
  While (b > 0)
      temp = b
	    b    = a % b
	    a    = temp
  Wend
  ProcedureReturn a
EndProcedure

Procedure.l ggTAsm(a.l, b.l) ; euclid in asm
  !MOV eax, [esp+4]       ; copy a to eax
  !AND eax, eax           ; set flags
  !JGE @f                 ; IF eax >= 0 then jump to @@
  !NEG eax                ; ELSE negate eax
  !@@:                    
  
  !MOV ebx, [esp+8]       ; copy b to ebx
  !AND ebx, ebx           ; set flags
  !JGE @f                 ; IF ebx >= 0 then jump to @@
  !NEG ebx                ; ELSE negate ebx
  !@@:                    
  
  !_ggtMyAsmWhile:
  !AND ebx, ebx           ; set flags
  !JLE _ggtMyAsmWend      ; jump to end on 0
  
  ; c = b
  !MOV ecx, ebx           ; save b to ecx
  ; b    = a % b 
  !XOR edx, edx           ; extend sign to edx with 0
  !IDIV ebx               ; div edx:eax / ebx
  !MOV ebx, edx           ; move rest to b
  
  ; a = c
  !MOV eax, ecx           ; move temp to a
  !JMP _ggtMyAsmWhile     ; loop
  !_ggtMyAsmWend: 
  
  ProcedureReturn         ; return eax
EndProcedure

Procedure.l GGT2(Zahl1.l, Zahl2.l) 
  
  If Zahl1 > 0 And Zahl2 > 0 
    While (Zahl1 <> Zahl2) 
      If Zahl1>Zahl2 
        Zahl1 = Zahl1-Zahl2 
      Else 
        Zahl2 = Zahl2-Zahl1 
      EndIf 
    Wend 
  EndIf 
  
  ProcedureReturn Zahl1 
  
EndProcedure

Procedure.l GGT2B(Zahl1.l, Zahl2.l) 
  
  Protected temp.l 
  
  If Zahl1 > 0 And Zahl2 > 0 
    While (Zahl1 > 0) 
      If Zahl1 > Zahl2 
        temp = Zahl1 
        Zahl1 = Zahl1 % Zahl2 
        Zahl2 = temp 
      Else 
        ;Tauschen 
        temp = Zahl1 
        Zahl1 = Zahl2 
        Zahl2 = temp 
      EndIf 
    Wend 
  EndIf 
  
  ProcedureReturn Zahl2 
  
EndProcedure

#N = 999999
Delay(0)

#MaxNumber = 10000000
RandomSeed(1000)
time1 = ElapsedMilliseconds() 
For z = 0 To #N 
  FindggT(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time1 = ElapsedMilliseconds() - time1 

RandomSeed(1000)
time2 = ElapsedMilliseconds() 
For z = 0 To #N 
  gcd(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time2 = ElapsedMilliseconds() - time2 

RandomSeed(1000)
time3 = ElapsedMilliseconds() 
For z = 0 To #N 
  gcd(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time3 = ElapsedMilliseconds() - time3

RandomSeed(1000)
time4 = ElapsedMilliseconds() 
For z = 0 To #N 
  ggT(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time4 = ElapsedMilliseconds() - time4 

RandomSeed(1000)
time5 = ElapsedMilliseconds() 
For z = 0 To #N 
  ggTAsm(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time5 = ElapsedMilliseconds() - time5

RandomSeed(1000)
time6 = ElapsedMilliseconds() 
For z = 0 To #N 
  GGT2(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time6 = ElapsedMilliseconds() - time6 

RandomSeed(1000)
time7 = ElapsedMilliseconds() 
For z = 0 To #N 
  GGT2B(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time7 = ElapsedMilliseconds() - time7 

SetClipboardText("FindggT: "+Str(time1)+" gcd: "+Str(time2)+ " gcdAsm: " + Str(time3) + " ggt: " + Str(time4)+ " ggtAsm: " + Str(time5) + " GGT2: " + Str(time6) + " GGT2B: " + Str(time7))
MessageRequester("", GetClipboardText())

Verfasst: 30.05.2006 01:49
von Deeem2031
Noch'n bisl schneller:

Code: Alles auswählen

Procedure FindggT(a,b) 
  Protected m=a 
  Protected n=b 
  Protected s=1 
  Protected t=0 
  Protected u=0 
  Protected v=1 
  
  While n>0 
    q=Round(m/n,0) ;Der Quotient wird abgerundet 
    r=m-q*n 
    m=n 
    n=r 
    tmp=u 
    u=s-q*u 
    s=tmp 
    tmp=v 
    v=t-q*v 
    t=tmp 
  Wend 
  
  ProcedureReturn m 
EndProcedure 

Procedure.l gcd(m.l, n.l) 
  Protected k.l = 0 
  
  If n < 0 : n * (-1) : EndIf 
  If m < 0 : m * (-1) : EndIf 
  
  While (m % 2 = 0 And n % 2 = 0) 
    m >> 1 
    n >> 1 
    k + 1 
  Wend 
  If n % 2 = 0 
    Swap m, n 
  EndIf 
  
  While m <> 0 
    While (m % 2 = 0) 
      m >> 1 
    Wend 
    
    If m < n 
      Swap m, n 
    EndIf 
    m - n 
  Wend 
  
  ProcedureReturn n * (1 << k) 
EndProcedure 

Procedure.l gcdAsm(m.l, n.l) 
  Protected k.l = 0 
  
  !MOV Eax, [p.v_m] 
  !AND Eax, Eax 
  !JGE @f 
  !NEG Eax 
  !@@: 
  !MOV Ecx, [p.v_n] 
  !AND Ecx, Ecx 
  !JGE @f 
  !NEG Ecx 
  !@@: 
  
  ; eax = m, ecx = n 
  !@@: 
  !MOV Edx, Eax 
  !AND Edx, 1 
  !JNZ @f 
  !MOV Edx, Ecx 
  !AND Edx, 1 
  !JNZ @f ;> 
    !SAR Eax, 1 
    !SAR Ecx, 1 
    !INC dword[p.v_k] 
    !JMP @b 
  !@@: ;< 
  
  !MOV Edx, Ecx 
  !AND Edx, 1 
  !JNZ @f ;> 
    !XCHG Eax, Ecx 
  !@@: ;< 
  
  ; eax = m, ecx = n 
  !@@: 
  !AND Eax, Eax 
  !JZ @f ;> 
    !.LOOP: 
    !MOV Edx, Eax 
    !AND Edx, 1 
    !JNZ .endloop ;> 
      !SAR Eax, 1 
      !JMP .LOOP 
    !.endloop: ;< 
    
    !CMP Eax, Ecx 
    !JNL .endif ;> 
      !XCHG Eax, Ecx 
    !.endif: ;< 
    
    !SUB Eax, Ecx 
  !JMP @b ;< 
  !@@: 
  
  !MOV Eax, Ecx 
  !MOV Edx, 1 
  !MOV Ecx, [p.v_k] 
  !SAL Edx, cl 
  !IMUL Eax, Edx 
  
  ProcedureReturn 
EndProcedure 

Procedure.l ggT(a.l, b.l) ; euclid 
  Protected temp.l 
  If a < 0 
    a = -a 
  EndIf 
  If b < 0 
    b = -b 
  EndIf 
  
  While (b > 0) 
      temp = b 
       b    = a % b 
       a    = temp 
  Wend 
  ProcedureReturn a 
EndProcedure 

Procedure.l ggTAsm(a.l, b.l) ; euclid in asm 
  !MOV eax, [esp+4]       ; copy a to eax 
  !AND eax, eax           ; set flags 
  !JGE @f                 ; IF eax >= 0 then jump to @@ 
  !NEG eax                ; ELSE negate eax 
  !@@:                    
  
  !MOV ebx, [esp+8]       ; copy b to ebx 
  !AND ebx, ebx           ; set flags 
  !JGE @f                 ; IF ebx >= 0 then jump to @@ 
  !NEG ebx                ; ELSE negate ebx 
  !@@:                    
  
  !_ggtMyAsmWhile: 
  !AND ebx, ebx           ; set flags 
  !JLE _ggtMyAsmWend      ; jump to end on 0 
  
  ; c = b 
  !MOV ecx, ebx           ; save b to ecx 
  ; b    = a % b 
  !XOR edx, edx           ; extend sign to edx with 0 
  !IDIV ebx               ; div edx:eax / ebx 
  !MOV ebx, edx           ; move rest to b 
  
  ; a = c 
  !MOV eax, ecx           ; move temp to a 
  !JMP _ggtMyAsmWhile     ; loop 
  !_ggtMyAsmWend: 
  
  ProcedureReturn         ; return eax 
EndProcedure 

Procedure.l ggTAsm2(a.l, b.l) ; euclid in asm 
  !MOV eax, [esp+4]       ; copy a to eax 
  !AND eax, eax           ; set flags 
  !JGE @f                 ; IF eax >= 0 then jump to @@ 
  !NEG eax                ; ELSE negate eax 
  !@@:                    
  
  !MOV ebx, [esp+8]       ; copy b to ebx 
  !AND ebx, ebx           ; set flags 
  !JGE @f                 ; IF ebx >= 0 then jump to @@ 
  !NEG ebx                ; ELSE negate ebx 
  !@@:                    
  
  !ggTAsm2_ggtMyAsmWhile: 
  !AND ebx, ebx           ; set flags 
  !JLE ggTAsm2_ggtMyAsmWend      ; jump to end on 0 
  
  !XOR edx, edx           ; extend sign to edx with 0 
  !IDIV ebx               ; div edx:eax / ebx 
  !MOV eax, ebx
  !MOV ebx, edx           ; move rest to b 

  !AND ebx, ebx           ; set flags 
  !JLE ggTAsm2_ggtMyAsmWend      ; jump to end on 0 
  
  !XOR edx, edx           ; extend sign to edx with 0 
  !IDIV ebx               ; div edx:eax / ebx 
  !MOV eax, ebx
  !MOV ebx, edx           ; move rest to b 
  
  !AND ebx, ebx           ; set flags 
  !JLE ggTAsm2_ggtMyAsmWend      ; jump to end on 0 

  !XOR edx, edx           ; extend sign to edx with 0 
  !IDIV ebx               ; div edx:eax / ebx 
  !MOV eax, ebx
  !MOV ebx, edx           ; move rest to b 

  !AND ebx, ebx           ; set flags 
  !JLE ggTAsm2_ggtMyAsmWend      ; jump to end on 0 
  
  !XOR edx, edx           ; extend sign to edx with 0 
  !IDIV ebx               ; div edx:eax / ebx 
  !MOV eax, ebx
  !MOV ebx, edx           ; move rest to b 
  
  !JMP ggTAsm2_ggtMyAsmWhile     ; loop 
  !ggTAsm2_ggtMyAsmWend: 
  
  ProcedureReturn         ; return eax 
EndProcedure 

Procedure.l GGT2(Zahl1.l, Zahl2.l) 
  
  If Zahl1 > 0 And Zahl2 > 0 
    While (Zahl1 <> Zahl2) 
      If Zahl1>Zahl2 
        Zahl1 = Zahl1-Zahl2 
      Else 
        Zahl2 = Zahl2-Zahl1 
      EndIf 
    Wend 
  EndIf 
  
  ProcedureReturn Zahl1 
  
EndProcedure 

Procedure.l GGT2B(Zahl1.l, Zahl2.l) 
  
  Protected temp.l 
  
  If Zahl1 > 0 And Zahl2 > 0 
    While (Zahl1 > 0) 
      If Zahl1 > Zahl2 
        temp = Zahl1 
        Zahl1 = Zahl1 % Zahl2 
        Zahl2 = temp 
      Else 
        ;Tauschen 
        temp = Zahl1 
        Zahl1 = Zahl2 
        Zahl2 = temp 
      EndIf 
    Wend 
  EndIf 
  
  ProcedureReturn Zahl2 
  
EndProcedure 

#N = 999999 
Delay(0) 

#MaxNumber = 10000000 
RandomSeed(1000) 
time1 = ElapsedMilliseconds() 
For z = 0 To #N 
  FindggT(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time1 = ElapsedMilliseconds() - time1 

RandomSeed(1000) 
time2 = ElapsedMilliseconds() 
For z = 0 To #N 
  gcd(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time2 = ElapsedMilliseconds() - time2 

RandomSeed(1000) 
time3 = ElapsedMilliseconds() 
For z = 0 To #N 
  gcd(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time3 = ElapsedMilliseconds() - time3 

RandomSeed(1000) 
time4 = ElapsedMilliseconds() 
For z = 0 To #N 
  ggT(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time4 = ElapsedMilliseconds() - time4 

RandomSeed(1000) 
time5 = ElapsedMilliseconds() 
For z = 0 To #N 
  ggTAsm(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time5 = ElapsedMilliseconds() - time5 

RandomSeed(1000) 
time6 = ElapsedMilliseconds() 
For z = 0 To #N 
  ggTAsm2(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time6 = ElapsedMilliseconds() - time6 

RandomSeed(1000) 
time7 = ElapsedMilliseconds() 
For z = 0 To #N 
  GGT2(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time7 = ElapsedMilliseconds() - time7 

RandomSeed(1000) 
time8 = ElapsedMilliseconds() 
For z = 0 To #N 
  GGT2B(Random(#MaxNumber)+1,Random(#MaxNumber)+1) 
Next 
time8 = ElapsedMilliseconds() - time8

SetClipboardText("FindggT: "+Str(time1)+" gcd: "+Str(time2)+ " gcdAsm: " + Str(time3) + " ggt: " + Str(time4)+ " ggtAsm: " + Str(time5)+ " ggtAsm2: " + Str(time6) + " GGT2: " + Str(time7) + " GGT2B: " + Str(time8)) 
MessageRequester("", GetClipboardText())

Verfasst: 30.05.2006 11:29
von Froggerprogger
Cheater! :wink: ...einfach die Loop zu entzerren... tststs

Verfasst: 30.05.2006 14:27
von Deeem2031
Froggerprogger hat geschrieben:Cheater! :wink: ...einfach die Loop zu entzerren... tststs
Nanana, ein Mov hab ich auch noch enfernt ;)

Verfasst: 30.05.2006 15:47
von DarkDragon
---------------------------

---------------------------
FindggT: 8171 gcd: 7742 gcdAsm: 7590 ggt: 3596 ggtAsm: 1111 ggtAsm2: 1112 GGT2: 37093 GGT2B: 10275
---------------------------
OK
---------------------------
Hat aber ewig gedauert.
Alle Zeiten sind UTC+02:00
Seite 2 von 3

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de