ggT->groesster geimensammer teiler

Hier könnt Ihr gute, von Euch geschriebene Codes posten. Sie müssen auf jeden Fall funktionieren und sollten möglichst effizient, elegant und beispielhaft oder einfach nur cool sein.
Antworten
Benutzeravatar
remi_meier
Beiträge: 1078
Registriert: 29.08.2004 20:11
Wohnort: Schweiz

Beitrag 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.
Zuletzt geändert von remi_meier am 30.05.2006 19:09, insgesamt 1-mal geändert.
Nach oben
Benutzeravatar
Karl
Beiträge: 520
Registriert: 21.07.2005 13:57
Wohnort: zu Hause

Beitrag 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
The Kopyright Liberation Front also known as the justified ancients of Mumu!
PB 5.X
Nach oben
Benutzeravatar
remi_meier
Beiträge: 1078
Registriert: 29.08.2004 20:11
Wohnort: Schweiz

Beitrag 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
Nach oben
Benutzeravatar
Deeem2031
Beiträge: 1232
Registriert: 29.08.2004 00:16
Wohnort: Vorm Computer
Kontaktdaten:
Kontaktdaten von Deeem2031

Beitrag 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 ;) )
Bild
[url=irc://irc.freenode.org/##purebasic.de]irc://irc.freenode.org/##purebasic.de[/url]
Nach oben
Benutzeravatar
remi_meier
Beiträge: 1078
Registriert: 29.08.2004 20:11
Wohnort: Schweiz

Beitrag 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:
Nach oben
Antworten

Zurück zu „Code, Tipps und Tricks“