Seite 1 von 3
ggT->groesster geimensammer teiler
Verfasst: 27.05.2006 21:41
von 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)
Verfasst: 28.05.2006 11:32
von 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))
Verfasst: 28.05.2006 12:25
von Konne
Nice one
Mit ein wenig ASM kann dass aber sicher noch jemand schlagen ...
Verfasst: 28.05.2006 23:19
von 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
Verfasst: 29.05.2006 08:16
von 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
Verfasst: 29.05.2006 11:14
von inc.
Warum wird eigentlich intern für ABS() nicht diese o.g. routine verwendet?
In der PB Doku steht, dass ABS() nur mit Floats funktioniert.
Verfasst: 29.05.2006 11:45
von 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.
Verfasst: 29.05.2006 13:58
von 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...
Verfasst: 29.05.2006 14:02
von Karl
Froggerprogger hat geschrieben:@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
Verfasst: 29.05.2006 14:03
von Karl
Froggerprogger hat geschrieben:@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