ggT->groesster geimensammer teiler

[Konne]

Diese Funktion ermittelt den ggT zweier Zahlen. Ich glaube nicht dass man viel daran rumoptimieren kann aber wenn ihr etwas findet, kein problem der Code gehoert euch :

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

Debug FindggT(28,98)

[remi_meier]

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


#N = 9999999
Delay(1000)

time1 = ElapsedMilliseconds()
For z = 0 To #N
  FindggT(28,98)
Next
time1 = ElapsedMilliseconds() - time1


time2 = ElapsedMilliseconds()
For z = 0 To #N
  gcd(28,98)
Next
time2 = ElapsedMilliseconds() - time2

MessageRequester("", "FindggT: "+Str(time1)+" gcd: "+Str(time2))

[Konne]

Nice one Mit ein wenig ASM kann dass aber sicher noch jemand schlagen ...

[Froggerprogger]

... und mit einem anderen Algo

Der Euklidische Algorithmus ist einen Tacken schneller.
Hier einmal mit und ohne ASM-Optimierungen

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


#N = 999999
Delay(0)

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

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

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

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

SetClipboardText("FindggT: "+Str(time1)+" gcd: "+Str(time2)+ " ggt: " + Str(time3)+ " ggtAsm: " + Str(time4))
MessageRequester("", GetClipboardText())

Speedtest bei mir:

FindggT: 1375 gcd: 437 ggt: 375 ggtAsm: 344

Aber vielleicht lässt sich gcd in asm noch so gut optimieren, dass er fixer ist ?


P.S.: gcd/ggt/ggtasm funktionieren auch mit negativen Zahlen (werden als positive genutzt) im Gegensatz zu findggt

[Karl]

Ein bisschen viel Code für ein kleineres Problem. Versucht mal

Code: Alles auswählen

;Euklid GGT

Procedure.l GGT(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

Keine Ahnung von ASM-Optimierungen.

[Nachtrag]

Ist ggT nicht für den Bereich der natürlichen Zahlen eingeschränkt?

Gruß Karl

[inc.]

Warum wird eigentlich intern für ABS() nicht diese o.g. routine verwendet?

Code: Alles auswählen

If a < 0
    a = -a
  EndIf

In der PB Doku steht, dass ABS() nur mit Floats funktioniert.

[Froggerprogger]

@Karl
Dein Algorithmus ist nicht der euklidische und gerade bei großen Zahlen relativ lahm. Die Modulo-Kiste scheint schneller zu approximieren. Hier ein paar Ergebnisse:

FindggT: 1484 gcd: 438 ggt: 390 ggtAsm: 344 GGT2: 812

@inc.
Seit Anbeginn meiner PB-Zeit (2.9) frage ich mich das schon und habe es auch schon ein paarmal im Feature-Forum gepostet. Auch plattformübergreifend sollte das kein Problem sein.

[Kaeru Gaman]

vielleicht blick ich jetzt auch die codes nicht.
per hand hab ich zum ermitteln von GGT/KGV immer in primfaktoren zerlegt. macht der algo das und seh ich bloss nich auf die schnelle?

re: ABS:
[editiert]

AbsW(Var) = ( Var & 7FFF )

AbsL(Var) = ( Var & 7FFFFFFF )

AbsQ(Var) = ( Var & 7FFFFFFFFFFFFFFF )


[nochn edit]
man könnte das in ein einziges macro packen, indem man die länge der variable im speicher ermittelt, und nur im höchstwertigen Byte das MSB löscht.

hab grad kein PB zur Hand, aber vielleicht mags ja jemand mal schnell machen und in der Macro-Thread in der T&T-Ecke packen...

[Karl]

@Karl
Dein Algorithmus ist nicht der euklidische

Das möchte ich mal bestreiten. Dieser ist der ursprüngliche - deiner offenbar die Erweiterung (wegen O(n)-Laufzeit).

Gruß Karl

[Karl]

@Karl
Dein Algorithmus ist nicht der euklidische

Das möchte ich mal bestreiten. Dieser ist der ursprüngliche - deiner offenbar die Erweiterung (wegen O(n)-Laufzeit).

Gruß Karl