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
Froggerprogger
Badmin
Beiträge: 855
Registriert: 08.09.2004 20:02

Beitrag von Froggerprogger »

Ach jau, sorry, es gibt ja den euklidischen und den erweiterten euklidischen Algorithmus, die beiden habe ich zusammengeworfen.
!UD2
Nach oben
Benutzeravatar
Karl
Beiträge: 520
Registriert: 21.07.2005 13:57
Wohnort: zu Hause

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

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
Nach oben
Benutzeravatar
inc.
Beiträge: 348
Registriert: 27.10.2004 12:25

Beitrag 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.
Nach oben
Benutzeravatar
inc.
Beiträge: 348
Registriert: 27.10.2004 12:25

Beitrag 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
Nach oben
Benutzeravatar
Froggerprogger
Badmin
Beiträge: 855
Registriert: 08.09.2004 20:02

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

Beitrag 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())
Bild
[url=irc://irc.freenode.org/##purebasic.de]irc://irc.freenode.org/##purebasic.de[/url]
Nach oben
Benutzeravatar
Froggerprogger
Badmin
Beiträge: 855
Registriert: 08.09.2004 20:02

Beitrag von Froggerprogger »

Cheater! :wink: ...einfach die Loop zu entzerren... tststs
!UD2
Nach oben
Benutzeravatar
Deeem2031
Beiträge: 1232
Registriert: 29.08.2004 00:16
Wohnort: Vorm Computer
Kontaktdaten:
Kontaktdaten von Deeem2031

Beitrag von Deeem2031 »

Froggerprogger hat geschrieben:Cheater! :wink: ...einfach die Loop zu entzerren... tststs
Nanana, ein Mov hab ich auch noch enfernt ;)
Bild
[url=irc://irc.freenode.org/##purebasic.de]irc://irc.freenode.org/##purebasic.de[/url]
Nach oben
DarkDragon
Beiträge: 6291
Registriert: 29.08.2004 08:37
Computerausstattung: Hoffentlich bald keine mehr
Kontaktdaten:
Kontaktdaten von DarkDragon

Beitrag von DarkDragon »

---------------------------

---------------------------
FindggT: 8171 gcd: 7742 gcdAsm: 7590 ggt: 3596 ggtAsm: 1111 ggtAsm2: 1112 GGT2: 37093 GGT2B: 10275
---------------------------
OK
---------------------------
Hat aber ewig gedauert.
Angenommen es gäbe einen Algorithmus mit imaginärer Laufzeit O(i * n), dann gilt O((i * n)^2) = O(-1 * n^2) d.h. wenn man diesen Algorithmus verschachtelt ist er fertig, bevor er angefangen hat.
Nach oben
Antworten

Zurück zu „Code, Tipps und Tricks“