PureBoard

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

ggT->groesster geimensammer teiler

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

Seite 3 von 3

Verfasst: 30.05.2006 17:41
von remi_meier
@Deeem2031: Unfair, du hast meine Asm-Proc gar nicht aufgerufen :lol:
aber egal, hab sie verbessert und den Test fairer gestaltet:

Code: Alles auswählen

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) 
  !PUSH Ebx
  !XOR Ecx, Ecx ; k = ecx
  
  ; negative Zahlen zu positiven wandeln
  !MOV Eax, [p.v_m+4]   ; laden in eax
  !AND Eax, Eax         ; Flags setzen
  !JGE @f ;>            ; wenn nicht negativ, springen
    !NEG Eax            ; eax = -eax
  !@@: ;<
  ; das Gleiche für n
  !MOV Ebx, [p.v_n+4]
  !AND Ebx, Ebx 
  !JGE @f ;> 
    !NEG Ebx 
  !@@: ;<
  
  ; eax = m, ebx = n 
  !@@:
  !MOV Edx, Eax ; Eax in temporäres Reg laden
  !OR Edx, Ebx  ; OR-Verknüpfung (v.a. das 1. Bit ist wichtig)
  !AND Edx, 1   ; Testen ob erstes Bit gesetzt (gerade oder ungerade Zahl)
  !JNZ @f ;>    ; wenn m oder n nicht gerade sind, springen
    !SAR Eax, 1 ; durch 2 dividieren
    !SAR Ebx, 1 
    !INC Ecx    ; k erhöhen
    !JMP @b     ; zurück zum Test
  !@@: ;< 
  
  !MOV Edx, Ebx   ; kleiner Test ob n gerade ist,
  !AND Edx, 1     ; wenn ja, dann m und n vertauschen,
  !JNZ @f ;>      ; bzw. eax und ebx
    !MOV Edx, Ebx ; Tausche
    !MOV Ebx, Eax
    !MOV Eax, Edx
  !@@: ;< 
  
  ; eax = m, ebx = n 
  !AND Eax, Eax   ; ist eax = 0?
  !JZ .endmain    ; wenn ja, dann fertig
  !@@: ;> 
    !.LOOP: 
    !MOV Edx, Eax     ; Test, ob m gerade ist
    !AND Edx, 1 
    !JNZ .endloop ;>  ; wenn gerade, dann ...
      !SAR Eax, 1     ; m / 2
      !JMP .LOOP      ; solange bis m ungerade ist
    !.endloop: ;< 
    
    !CMP Eax, Ebx     ; wenn m < n, dann...
    !JNL .endif ;> 
      !MOV Edx, Ebx   ; vertausche m und n
      !MOV Ebx, Eax
      !MOV Eax, Edx
    !.endif: ;< 
    
    !SUB Eax, Ebx     ; m = m - n
  !JNZ @b ;<          ; wenn m = 0, dann ist fertig, sonst zurückspringen
  !.endmain: 
  
  ; ebx = n, ecx = k
  !MOV Eax, 1      ; 1 nach Eax für Bitshifting
  !SAL Eax, cl     ; die 1 k-mal nach links shiften = 2^k
  !IMUL Eax, Ebx   ; multiplizieren mit n, returnvalue in Eax
  
  !POP Ebx
  ProcedureReturn  ; Eax zurückgeben
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 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 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 = 599999
Delay(0) 

#MaxNumber = 10000000 
Dim rnd.l(2000)
RandomSeed(1000)
For z = 0 To 2000
  rnd(z) = Random(#MaxNumber)
Next


time2 = ElapsedMilliseconds() 
For z = 0 To #N 
  a = rnd(z%2001)
  b = rnd((z+1)%2001)
  gcd(a,b) 
  gcd(a,b) 
  gcd(a,b) 
  gcd(a,b) 
  gcd(a,b) 
Next 
time2 = ElapsedMilliseconds() - time2 


time3 = ElapsedMilliseconds() 
For z = 0 To #N 
  a = rnd(z%2001)
  b = rnd((z+1)%2001)
  gcdAsm(a,b) 
  gcdAsm(a,b) 
  gcdAsm(a,b) 
  gcdAsm(a,b) 
  gcdAsm(a,b)  
Next 
time3 = ElapsedMilliseconds() - time3 


time4 = ElapsedMilliseconds() 
For z = 0 To #N 
  a = rnd(z%2001)
  b = rnd((z+1)%2001)
  ggT(a,b) 
  ggT(a,b) 
  ggT(a,b) 
  ggT(a,b) 
  ggT(a,b)  
Next 
time4 = ElapsedMilliseconds() - time4 




time6 = ElapsedMilliseconds() 
For z = 0 To #N 
  a = rnd(z%2001)
  b = rnd((z+1)%2001)
  ggTAsm2(a,b) 
  ggTAsm2(a,b) 
  ggTAsm2(a,b) 
  ggTAsm2(a,b) 
  ggTAsm2(a,b)  
Next 
time6 = ElapsedMilliseconds() - time6 



time8 = ElapsedMilliseconds() 
For z = 0 To #N 
  a = rnd(z%2001)
  b = rnd((z+1)%2001)
  GGT2B(a,b) 
  GGT2B(a,b) 
  GGT2B(a,b) 
  GGT2B(a,b) 
  GGT2B(a,b) 
Next 
time8 = ElapsedMilliseconds() - time8 

SetClipboardText("gcd: "+Str(time2)+ " gcdAsm: " + Str(time3) + " ggt: " + Str(time4)+ " ggtAsm2: " + Str(time6)+ " GGT2B: " + Str(time8)) 
MessageRequester("", GetClipboardText())
---------------------------

---------------------------
gcd: 1078 gcdAsm: 640 ggt: 985 ggtAsm2: 937 GGT2B: 1141
---------------------------
OK
---------------------------
Man bemerke: noch keine Looperweiterung bei mir!

Edit: dämliche Verbesserung vorgenommen.

Verfasst: 30.05.2006 18:07
von Karl
Der Shifter-Algorithmus wird wohl der schnellste bleiben (0(n log n)).

Vielleicht könnte man den best case (eine Zahl ist Teiler der anderen Zahl) noch abfangen, um einen besseren average case zu bekommen.

Gruß Karl

Verfasst: 30.05.2006 18:35
von remi_meier
Mal abwarten :)
Ich habe die Prozedur nun noch kommentiert für alle, die Assembler
lernen wollen. Wenns Beanstandungen gibt, einfach posten (was sonst).

Code: Alles auswählen

Procedure.l gcdAsm(m.l, n.l) 
  !PUSH Ebx
  !XOR Ecx, Ecx ; k = ecx
  
  ; negative Zahlen zu positiven wandeln
  !MOV Eax, [p.v_m+4]   ; laden in eax
  !AND Eax, Eax         ; Flags setzen
  !JGE @f ;>            ; wenn nicht negativ, springen
    !NEG Eax            ; eax = -eax
  !@@: ;<
  ; das Gleiche für n
  !MOV Ebx, [p.v_n+4]
  !AND Ebx, Ebx 
  !JGE @f ;> 
    !NEG Ebx 
  !@@: ;<
  
  ; eax = m, ebx = n 
  !@@:
  !MOV Edx, Eax ; Eax in temporäres Reg laden
  !OR Edx, Ebx  ; OR-Verknüpfung (v.a. das 1. Bit ist wichtig)
  !AND Edx, 1   ; Testen ob erstes Bit gesetzt (gerade oder ungerade Zahl)
  !JNZ @f ;>    ; wenn m oder n nicht gerade sind, springen
    !SAR Eax, 1 ; durch 2 dividieren
    !SAR Ebx, 1 
    !INC Ecx    ; k erhöhen
    !JMP @b     ; zurück zum Test
  !@@: ;< 
  
  !MOV Edx, Ebx   ; kleiner Test ob n gerade ist,
  !AND Edx, 1     ; wenn ja, dann m und n vertauschen,
  !JNZ @f ;>      ; bzw. eax und ebx
    !MOV Edx, Ebx ; Tausche
    !MOV Ebx, Eax
    !MOV Eax, Edx
  !@@: ;< 
  
  ; eax = m, ebx = n 
  !AND Eax, Eax   ; ist eax = 0?
  !JZ .endmain    ; wenn ja, dann fertig
  !@@: ;> 
    !.LOOP: 
    !MOV Edx, Eax     ; Test, ob m gerade ist
    !AND Edx, 1 
    !JNZ .endloop ;>  ; wenn gerade, dann ...
      !SAR Eax, 1     ; m / 2
      !JMP .LOOP      ; solange bis m ungerade ist
    !.endloop: ;< 
    
    !CMP Eax, Ebx     ; wenn m < n, dann...
    !JNL .endif ;> 
      !MOV Edx, Ebx   ; vertausche m und n
      !MOV Ebx, Eax
      !MOV Eax, Edx
    !.endif: ;< 
    
    !SUB Eax, Ebx     ; m = m - n
  !JNZ @b ;<          ; wenn m = 0, dann ist fertig, sonst zurückspringen
  !.endmain: 
  
  ; ebx = n, ecx = k
  !MOV Eax, 1      ; 1 nach Eax für Bitshifting
  !SAL Eax, cl     ; die 1 k-mal nach links shiften = 2^k
  !IMUL Eax, Ebx   ; multiplizieren mit n, returnvalue in Eax
  
  !POP Ebx
  ProcedureReturn  ; Eax zurückgeben
EndProcedure

Verfasst: 30.05.2006 20:44
von Deeem2031
Beanstandung #1:

Code: Alles auswählen

    !MOV Edx, Eax     ; Test, ob m gerade ist 
    !AND Edx, 1
->

Code: Alles auswählen

    !TEST Eax, 1
(weitere folgen ;) )

Verfasst: 30.05.2006 21:29
von remi_meier
Stimmt, das TEST habe ich bisher so selten benötigt...
Du darfst gerne den ganzen Code überarbeiten und nochmals komplett
posten, immerhin optimierst du jetzt am richtigen Code rum :wink:
Alle Zeiten sind UTC+02:00
Seite 3 von 3

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de