Der euklidische Algorithmus (berechnet gcd ) ist sehr schnell. Wenn zwei Zahlen zufällig aus [1, n] gezogen werden, beträgt die durchschnittliche Anzahl der Schritte zum Berechnen ihrer gcd O(log n) . Die durchschnittliche Rechenzeit für jeden Schritt ist quadratisch in der Anzahl der Ziffern.
Es gibt Alternativen, die etwas besser funktionieren (d. h. jeder Schritt ist in der Anzahl der Ziffern subquadratisch), aber sie sind nur bei sehr großen ganzen Zahlen wirksam. Siehe zum Beispiel Über Schönhages Algorithmus und subquadratische ganzzahlige gcd-Berechnung .
Wenn Sie auf einer Maschine arbeiten, deren Divisionen / Residuen wesentlich teurer sind als Shifts, sollten Sie binary GCD in Erwägung ziehen .
Tags und Links algorithm number-theory greatest-common-divisor