Was ist für GCD am effizientesten?

26

Ich weiß, dass der Algorithmus von Euclid der beste Algorithmus ist, um den GCD (Great Common Divisor) einer Liste positiver Ganzzahlen zu erhalten. In der Praxis können Sie diesen Algorithmus jedoch auf verschiedene Arten codieren. (In meinem Fall habe ich mich für Java entschieden, aber C / C ++ könnte eine andere Option sein).

Ich muss den effizientesten Code in meinem Programm verwenden.

Im rekursiven Modus können Sie schreiben:

static long gcd (long a, long b){
    a = Math.abs(a); b = Math.abs(b);
    return (b==0) ? a : gcd(b, a%b);
  }

Und im iterativen Modus sieht es so aus:

static long gcd (long a, long b) {
  long r, i;
  while(b!=0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

Es gibt auch den Binäralgorithmus für die GCD, der einfach so codiert werden kann:

int gcd (int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}
Jonaprieto
quelle
3
Ich finde das zu subjektiv und vielleicht sogar besser für StackOverflow geeignet. "In der Praxis am effizientesten" hängt von vielen (sogar unvorhersehbaren) Faktoren ab, wie der zugrunde liegenden Architektur, der Speicherhierarchie, der Größe und Form der Eingabe usw.
Juho,
5
Dies ist der gleiche Algorithmus, der auf rekursive und iterative Weise ausgedrückt wird. Ich denke, ihr Unterschied ist vernachlässigbar, da der Euklid-Algorithmus ziemlich schnell konvergiert. Wählen Sie eine, die Ihren Wünschen entspricht.
Pad
6
Vielleicht möchten Sie versuchen, diese beiden zu profilieren. Da es sich bei der rekursiven Version um einen Tail Call handelt, ist es nicht unwahrscheinlich, dass der Compiler tatsächlich fast denselben Code ausgibt.
Louis
1
das ist falsch. sollte sein, während b! = 0 ist, und dann a zurückgeben. Andernfalls geht es bei der Division durch Null schief. Verwenden Sie auch keine Rekursion, wenn Sie wirklich große gcds haben ... Sie erhalten einen Stapel von Stapel- und Funktionszuständen ... warum nicht einfach iterativ?
Cris Stringfellow
4
Beachten Sie, dass es asymptotisch schnellere GCD-Algorithmen gibt. ZB en.wikipedia.org/wiki/Binary_GCD_algorithm
Neal Young

Antworten:

21

Ihre beiden Algorithmen sind äquivalent (zumindest für positive Ganzzahlen, was mit negativen Ganzzahlen in der imperativen Version passiert, hängt von Javas Semantik ab, %die ich nicht auswendig kann). In der rekursiven Version sei und b i das Argument des i- ten rekursiven Aufrufs: a i + 1 = b i b i + 1 = a i m o d b ieinichbichich

einich+1=bichbich+1=einichmOdbich

In der imperativen Version sei und b ' i der Wert der Variablen und am Anfang der i- ten Iteration der Schleife. a ' i + 1 = b ' i b ' i + 1 = a ' i m o d b ' ieinichbichabich

einich+1=bichbich+1=einichmOdbich

Beachten Sie eine Ähnlichkeit? Ihre imperative Version und Ihre rekursive Version berechnen genau dieselben Werte. Außerdem enden beide zur gleichen Zeit, wenn (bzw. a ' i = 0 ), so dass sie die gleiche Anzahl von Iterationen ausführen. Algorithmisch gesehen gibt es also keinen Unterschied zwischen den beiden. Jeder Unterschied ist eine Frage der Implementierung, die in hohem Maße vom Compiler, der Hardware, auf der er ausgeführt wird, und möglicherweise vom Betriebssystem und den gleichzeitig ausgeführten Programmen abhängt.einich=0einich=0

Die rekursive Version führt nur rekursive Tail-Aufrufe aus . Die meisten Compiler für imperative Sprachen optimieren diese nicht. Daher ist es wahrscheinlich, dass der von ihnen generierte Code bei jeder Iteration ein wenig Zeit und Speicher verschwendet, um einen Stapelrahmen zu erstellen. Mit einem Compiler, der Tail Calls optimiert (Compiler für funktionale Sprachen fast immer), kann der generierte Maschinencode für beide gleich sein (vorausgesetzt, Sie harmonisieren diese Aufrufe abs).

Gilles 'SO - hör auf böse zu sein'
quelle
8

Für kleine Zahlen reicht der binäre GCD-Algorithmus aus.

GMP, eine gut gewartete und in der Praxis getestete Bibliothek, wird nach dem Überschreiten eines bestimmten Schwellenwerts, einer Verallgemeinerung von Lehmers Algorithmus, auf einen speziellen Halb-GCD-Algorithmus umstellen. Lehmers verwendet eine Matrixmultiplikation, um die Standard-Euklidian-Algorithmen zu verbessern. Gemäß den Dokumenten ist die asymptotische Laufzeit von sowohl HGCD als auch GCD O(M(N)*log(N)), wobei M(N)die Zeit zum Multiplizieren von zwei N-Glied-Zahlen ist.

Alle Details zu ihrem Algorithmus finden Sie hier .

qwr
quelle
Der Link bietet wirklich keine vollständigen Details und definiert nicht einmal, was ein "Glied" ist ...
einpoklum - wieder Monica
2

Wie ich weiß, unterstützt Java im Allgemeinen keine Schwanzrekursionsoptimierung, aber Sie können Ihre Java-Implementierung dafür testen. Wenn dies nicht unterstützt wird, sollte eine einfache forSchleife schneller sein, andernfalls sollte die Rekursion genauso schnell sein. Auf der anderen Seite handelt es sich um Bit-Optimierungen. Wählen Sie den Code, den Sie für einfacher und besser lesbar halten.

Ich sollte auch beachten , dass der schnellste GCD Algorithmus ist nicht Euklids Algorithmus, Lehmer-Algorithmus ist ein bisschen schneller.

PJTraill
quelle
Meinst du so weit ich weiß ? Meinen Sie, dass die Sprachspezifikation diese Optimierung nicht vorschreibt (es wäre überraschend, wenn dies der Fall wäre), oder dass die meisten Implementierungen sie nicht implementieren?
PJTraill
1

Verwenden Sie zunächst keine Rekursivität, um eine enge Schleife zu ersetzen. Es ist langsam. Verlassen Sie sich nicht auf den Compiler, um es zu optimieren. Zweitens rufen Sie in Ihrem Code in jedem rekursiven Aufruf Math.abs () auf, was unbrauchbar ist.

In Ihrer Schleife können Sie auf einfache Weise temporäre Variablen vermeiden und die ganze Zeit a und b tauschen.

int gcd(int a, int b){
    if( a<0 ) a = -a;
    if( b<0 ) b = -b;
    while( b!=0 ){
        a %= b;
        if( a==0 ) return b;
        b %= a;
    }
    return a;
}

Durch das Vertauschen mit a ^ = b ^ = a ^ = b wird die Quelle kürzer, die Ausführung erfordert jedoch viele Anweisungen. Es ist langsamer als der langweilige Tausch mit einer temporären Variablen.

Florian F
quelle
3
„Vermeiden Sie Rekursivität. Es ist langsam “- als allgemeiner Rat, das ist Schwindel. Das hängt vom Compiler ab. Selbst bei Compilern, die die Rekursion nicht optimieren, ist dies in der Regel nicht langsam, sondern nur stapelintensiv.
Gilles 'SO - hör auf böse zu sein'
3
Bei einem solchen Funktionscode ist der Unterschied jedoch erheblich. Stapeln bedeutet, in den Speicher zu schreiben und daraus zu lesen. Das ist langsam Der obige Code wird in 2 Registern ausgeführt. Rekursivität bedeutet auch, Anrufe zu tätigen, was länger ist als ein bedingter Sprung. Ein rekursiver Aufruf ist für die Verzweigungsvorhersage viel schwieriger und schwieriger inline.
Florian F
-2

Für kleine Zahlen ist% eine ziemlich teure Operation, vielleicht die einfachere rekursive

GCD[a,b] := Which[ 
   a==b , Return[a],
   b > a, Return[ GCD[a, b-a]],
   a > b, Return[ GCD[b, a-b]]
];

ist schneller? (Sorry, Mathematica-Code und nicht C ++)

Per Alexandersson
quelle
Es sieht nicht richtig aus. Für b == 1 sollte es 1 zurückgeben. Und GCD [2,1000000000] wird langsam sein.
Florian F
Ah ja, ich habe einen Fehler gemacht. Behoben (glaube ich) und geklärt.
Per Alexandersson
Normalerweise sollte GCD [a, 0] auch a zurückgeben. Deine Loops für immer.
Florian F
Ich stimme ab, da Ihre Antwort nur Code enthält. Wir konzentrieren uns gerne auf die Ideen auf dieser Site. Warum ist% beispielsweise eine teure Operation? Spekulationen über ein Stück Code sind meiner Meinung nach keine wirklich gute Antwort für diese Site.
Juho
1
Ich denke, die Idee, dass Modulo langsamer ist als Subtraktion, kann als Folklore betrachtet werden. Es gilt sowohl für kleine Ganzzahlen (Subtraktion dauert normalerweise einen Zyklus, Modulo selten) als auch für große Ganzzahlen (Subtraktion ist linear, ich bin mir nicht sicher, was die beste Komplexität für Modulo ist, aber es ist definitiv schlimmer). Natürlich müssen Sie auch die Anzahl der erforderlichen Iterationen berücksichtigen.
Gilles 'SO- hör auf böse zu sein'
-2

Der Euklid-Algorithmus ist am effizientesten für die Berechnung von GCD:

Statische Long GCD (Long A, Long B)
{
if (b == 0)
return a;
sonst
return gcd (, a% b);
}

Beispiel:-

Sei A = 16, B = 10.
GCD (16, 10) = GCD (10, 16% 10) = GCD (10, 6)
GCD (10, 6) = GCD (6, 10% 6) = GCD (6, 4)
GCD (6, 4) = GCD (4, 6% 4) = GCD (4, 2)
GCD (4, 2) = GCD (2, 4% 2) = GCD (2, 0)


Da B = 0 ist, gibt GCD (2, 0) 2 zurück. 
Rohit-Pandey
quelle
4
Dies beantwortet die Frage nicht. Der Fragesteller präsentiert zwei Versionen von Euclid und fragt, welche schneller ist. Sie scheinen das nicht bemerkt zu haben und deklarieren die rekursive Version lediglich als den einzigen Euklid-Algorithmus und behaupten, dass sie schneller ist als alles andere.
David Richerby