Algorithmen sind eines der zentralen Themen in der
Programmierung , sie sind überall (besonders in Interviews, haha).
(Kann man in einem solchen Beitrag auf ein Knopfakkordeon verzichten?)Einer der bekanntesten ist der sogenannte
euklidische Algorithmus - vielleicht der häufigste Weg, um den
größten gemeinsamen Teiler (GCD) zweier nicht negativer Ganzzahlen zu finden. Oft beginnt er auch, die relevanten Bereiche der
Mathematik und
Informatik zu studieren (und zu lernen).
Und
Donald Knuth , der bekannte Autor der Abhandlung „Die
Kunst des Programmierens “ (und nicht nur), betrachtet den Algorithmus sogar als den ersten in der Geschichte (zumindest in Bezug auf moderne Definitionen). Denn trotz der Tatsache, dass der Algorithmus vor
Euklid erfunden und verwendet wurde, lebte er in den IV-III Jahrhunderten. BC (es wurde bereits von
Aristoteles erwähnt , der ein Jahrhundert zuvor lebte), beschreibt Euklid den Prozess
iterativ , was mit der modernen Bedeutung des Wortes übereinstimmt.
Das Wort „Algorithmus“ geht auf den Namen des persischen Mathematikers
Al-Khwarizmi zurück , der um das VIII-IX Jahrhundert lebte. schon AD. Und der Beginn seiner Verwendung in einem modernen Sinne wird nur als das 20. Jahrhundert betrachtet, genauer gesagt - seine ersten Jahrzehnte, der Aufstieg der Informationstechnologie.
Euklidischer Algorithmus
Aus Neugier empfehle ich Ihnen, sich mit der euklidischen Beschreibung des Algorithmus in Knuths Bearbeitung vertraut zu machen. Es ist ziemlich lang, daher unter dem Schnitt versteckt:
Beschreibung des euklidischen Algorithmus in der Nähe des OriginalsAngebot. Finden Sie für zwei positive ganze Zahlen ihren größten gemeinsamen Teiler.
Sei A und C zwei gegebene positive ganze Zahlen; Es ist erforderlich, ihre GCD zu finden. Wenn die Zahl A durch C teilbar ist, ist die Zahl C ein gemeinsamer Teiler der Zahlen C und A, da sie sich selbst teilt. Und natürlich wird es der größte Teiler sein, da es keine größere Zahl als die Zahl C gibt, die C teilt.
Wenn C die Zahl A nicht teilt, subtrahieren wir kontinuierlich die kleinere der Zahlen A und C von der größeren, bis wir eine Zahl erhalten, die die vorherige subtrahierte Zahl vollständig teilt. Dies sollte früher oder später geschehen, denn wenn die Differenz gleich eins ist, teilt die Einheit den zuvor subtrahierten Wert.
Nehmen wir nun an, dass E der positive Rest der Division der Zahl A durch C ist; Sei F der positive Rest der Division von C durch E und sei F die Division von E. Da F E und E C - F teilt, teilt F auch C - F. Aber es teilt sich auch selbst, also teilt F C, und C teilt A - E; daher teilt F auch A - E, aber es teilt auch E; daher teilt F A. Folglich ist F ein gemeinsamer Teiler der Zahlen A und C.
Jetzt bestätige ich, dass es sich auch um eine GCD handelt. Wenn F nicht der größte gemeinsame Teiler der Zahlen A und C ist, gibt es tatsächlich eine größere Zahl, die diese beiden Zahlen teilt. Sei diese Zahl G.
Da die Zahl G die Zahl C teilt und die Zahl C A - E teilt, teilt G auch die Zahl A - E. Die Zahl G teilt auch die ganze Zahl A, so dass sie den Rest E teilt. Aber E teilt C - F, also G. teilt auch C - F. Und die Zahl G teilt auch die ganze Zahl C, da sie den Rest F teilt; somit teilt eine größere Zahl eine kleinere, und dies ist unmöglich.
Somit gibt es keine Zahl größer als F, die A und C teilt; daher ist die Zahl F GCD.
Folge Diese Argumentation macht die Annahme offensichtlich, dass jede Zahl, die zwei Zahlen teilt, ihre GCD teilt. Rt
Die Beschreibung gibt zwei Möglichkeiten, um GCD zu finden - durch Subtraktion und Division. Tatsächlich sind diese beiden Methoden zur Implementierung des Algorithmus heute weithin bekannt.
Hier ist ein Beispiel für eine in
Swift geschriebene Funktion, die die erste Methode implementiert:
func subtractionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber while firstNumber != 0, secondNumber != 0 { if firstNumber > secondNumber { firstNumber = firstNumber - secondNumber } else { secondNumber = secondNumber - firstNumber } } return firstNumber + secondNumber
Hier habe ich zur Wiederverwendung, um meinetwillen, die Fälle der Suche nach GCD, wenn sie sofort bekannt sind, in eine separate Funktion gebracht, ohne dass ein Algorithmus befolgt werden muss:
func simpleCasesGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int? { if firstNumber == secondNumber { return firstNumber
(Wenn zwei Zahlen gleich sind, ist natürlich auch ihre GCD gleich. Wenn eine der Zahlen Null ist, ist die GCD gleich der zweiten Zahl, da Null durch eine beliebige Zahl teilbar ist (mit dem Ergebnis natürlich auch Null). .)
Als Eingabe können nur nicht negative Werte verwendet werden. Dementsprechend können Sie für das Negativ die gleichen Methoden verwenden, jedoch die Zahlen modulo nehmen. (Ja, der gemeinsame Faktor kann auch negativ sein, aber wir suchen speziell nach GCD, und positive Zahlen sind offensichtlich immer mehr als negativ.)
Und hier kann es so aussehen, als würde die Version des Algorithmus nach Division implementiert:
func divisionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber while firstNumber != 0, secondNumber != 0 { if firstNumber > secondNumber { firstNumber = firstNumber % secondNumber } else { secondNumber = secondNumber % firstNumber } } return firstNumber + secondNumber
Die zweite Version wird heute als vorzuziehen angesehen, da sie im Durchschnitt eine wesentlich geringere Anzahl von Schritten enthält. In einer Zeit, in der Computer groß und langsam waren, konnte der Teilungsvorgang jedoch ein komplexer Vorgang für sich sein. Und dann könnte die erste Version des Algorithmus effektiver sein.
Um sie ein wenig zu vergleichen, habe ich mehrere Messungen mit der
measure(_:) -Methode meiner
XCTestCase Klasse des "nativen" Frameworks zum Testen von Code in
Xcode- Projekten von
XCTest .
Als Eingabe habe ich ein Array von Paaren von Zufallszahlen verwendet. Die Messungen wurden natürlich unter Verwendung des gleichen Arrays für jede Methode durchgeführt. Ich habe die Verteilung der Zahlen für Paare von null auf 9999 genommen. Die Anzahl der Berechnungen (Zahlenpaare) wurde gemessen: eins, zehn, 100, 1000, 10000, 100000, 1.000.000 und 10.000.000. Letzteres ließ mich das Ergebnis für einige Minuten erwarten, also entschied ich mich dafür aufhören.
Hier ist ein einfacher Code zur Eingabegenerierung:
let pairs = (0..<100).map { _ in (Int.random(in: 0..<10000), Int.random(in: 0..<10000)) }
Die Messung selbst sieht zum Beispiel so aus:
func testSubstractionGCDPerformance() { measure() { _ = pairs.map { substractionGCD($0, $1) } } }
Und hier sind die Ergebnisse des Starts auf meinem Computer:
(Subtraktion - Subtraktion, Division - Division.)Im Allgemeinen ist sehr deutlich zu erkennen, wie viel die Subtraktionsmethode auf modernen Computern verliert.
"Verbesserte" Version des euklidischen Algorithmus
In der Literatur finden Sie eine Version des Algorithmus, bei der eine der Zahlen in jedem Schritt anstelle des Restes der Division durch die Sekunde durch die Differenz zwischen diesem Versatz und der zweiten Zahl ersetzt wird, jedoch nur, wenn der Rest der Division mehr als die Hälfte der zweiten Zahl beträgt. Eine Implementierung dieser Version könnte folgendermaßen aussehen:
func improvedDivisionGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber while firstNumber != 0, secondNumber != 0 { if firstNumber > secondNumber { let firstNumberClaim = firstNumber % secondNumber if firstNumberClaim > secondNumber / 2 { firstNumber = abs(firstNumberClaim - secondNumber) } else { firstNumber = firstNumberClaim } } else { let secondNumberClaim = secondNumber % firstNumber if secondNumberClaim > firstNumber / 2 { secondNumber = abs(secondNumberClaim - firstNumber) } else { secondNumber = secondNumberClaim } } } return firstNumber + secondNumber
Eine solche Änderung reduziert die Anzahl der Schritte im Algorithmus, aber nach den Ergebnissen der Messungen auf meinem Computer zu urteilen, neutralisieren zusätzliche Berechnungen und Überprüfungen bei jedem Schritt diesen Vorteil und noch mehr:
(Verbessert ist die "verbesserte" Version.)Ein bisschen mehr über die Bedeutung des euklidischen Algorithmus
Der Algorithmus hat auch eine geometrische Version (um das größte Maß aus zwei Segmenten zu finden).
Der Algorithmus wurde natürlich verallgemeinert, um GCD mit einer beliebigen Anzahl von Zahlen zu finden, nicht nur mit zwei. Kurz gesagt lautet die Idee: Wenn wir die Funktion der Suche nach der GCD von zwei Zahlen als gcd (a, b) bezeichnen, dann ist die GCD von drei Zahlen gcd (a, b, c) gleich gcd (gcd (a, b), c). Und so weiter wird für eine beliebige Anzahl von Zahlen die GCD gefunden, indem die GCD der GCD des vorherigen Zahlenpaars und der nächsten Zahl nacheinander berechnet wird. Dies betrifft natürlich die Suche nach GCD im Allgemeinen und nicht nur den euklidischen Algorithmus.
Es gibt auch eine Verallgemeinerung des Algorithmus zum Auffinden von GCD-Polynomen. Dies geht jedoch bereits über den Rahmen dieses einfachen Beitrags und in gewissem Maße über meine mathematischen Kenntnisse hinaus.
Komplexität des euklidischen Algorithmus
Die zeitliche Komplexität des Algorithmus wurde lange Zeit untersucht, nicht schnell und von viel gelehrteren Männern als Ihrem bescheidenen Diener. Die Frage ist jedoch seit langem geschlossen und eine Antwort ist eingegangen. Eigentlich schon in der Mitte des vorletzten Jahrhunderts.
Gabriel Lame .
Kurz gesagt, die Antwort wird tatsächlich durch den Lame-Satz formuliert, der sich auf diesen Algorithmus bezieht. Die Anzahl der Schritte im Algorithmus entspricht der Sequenznummer der nächstgrößeren
Fibonacci-Zahl, der kleinsten der beiden Anzahlen von Eingabeparametern minus 2. Unter Verwendung einer etwas traditionelleren mathematischen Notation beträgt die Anzahl der Durchgänge des Algorithmus n - 2, wenn u> v (und v> 1) v <Fn (Fn ist die nächste v Fibonacci-Zahl und n ist ihre Sequenznummer).
Fibonacci-Zahlen wachsen exponentiell, wir haben eine logarithmische Funktion der Ausführungszeit des Algorithmus (aus der kleineren der beiden Eingangszahlen).
Dieselben Berechnungen zeigen, dass die schlechtesten Eingabedaten für den Algorithmus zwei aufeinanderfolgende Fibonacci-Zahlen sind.
Binäre Methode zum Auffinden von NOD
In Bezug auf die Suche nach GCD ist der bereits in den 60er Jahren des letzten Jahrhunderts von einem bestimmten Joseph Stein vorgeschlagene Algorithmus zu erwähnen, über den ich im Internet überhaupt keine Informationen gefunden habe. Es (der Algorithmus) ist auf
binäre Arithmetik ausgerichtet und enthält keine Divisionsoperationen. Der Algorithmus arbeitet nur mit Paritätsprüfungen und Halbierungen, was allein mit den Fähigkeiten der binären Arithmetik möglich ist.
Der Algorithmus basiert auf vier Fakten:
- Wenn u und v beide gerade sind, dann ist gcd (u, v) = 2 · gcd (u / 2, v / 2);
- Wenn u gerade ist und v nicht, ist gcd (u, v) = gcd (u / 2, v);
- gcd (u, v) = gcd (u - v, v) (dies folgt aus dem euklidischen Algorithmus);
- Wenn u und v beide ungerade sind, ist u - v gerade und | u - v | <max (u, v)
Auf Wikipedia können Sie die rekursive Version des Algorithmus sehen (in modernen Programmiersprachen in mehreren Zeilen geschrieben). Ich habe ihn in Swift nicht umgeschrieben. Und hier gebe ich eine iterative Implementierung:
func binaryGCD(_ firstNumber: Int, _ secondNumber: Int) -> Int { if let simpleGCD = simpleCasesGCD(firstNumber, secondNumber) { return simpleGCD } var firstNumber = firstNumber var secondNumber = secondNumber var shift = 0 while (firstNumber | secondNumber) & 1 == 0 { shift += 1 firstNumber >>= 1 secondNumber >>= 1 } while firstNumber & 1 == 0 { firstNumber >>= 1 } repeat { while secondNumber & 1 == 0 { secondNumber >>= 1 } if firstNumber > secondNumber { swap(&firstNumber, &secondNumber) } secondNumber -= firstNumber } while secondNumber != 0 return firstNumber << shift }
Nachdem dieser hochentwickelte Algorithmus auf meinem Computer Messungen an denselben Daten durchgeführt hatte, entsprach er leider nicht den an ihn gestellten Erwartungen. Natürlich arbeitet es immer noch doppelt so schnell wie der euklidische Algorithmus durch Subtraktion, ist aber seiner klassischen Divisionsversion deutlich unterlegen. Vollständige Übersichtstabelle:
(Binär ist ein binärer Algorithmus.)(Ich schließe nicht aus, dass der Algorithmus effizienter geschrieben werden kann als ich, und dies wirkt sich auf das Ergebnis aus, aber wofür brauchen wir dann Compiler?!
Übrigens war dieser Algorithmus, der zweifellos bereits im Zeitalter der Informationstechnologie (früher als heute) 15 Minuten lang berühmt wurde, im alten China bekannt. Seine Beschreibung findet sich in Werken aus dem 1. Jahrhundert. AD Natürlich in Begriffen wie "halbe Division" und Subtraktion. Und auch im Zusammenhang mit der Reduzierung von Brüchen.
Fazit
Ehrlich gesagt, mit dieser einfachen "Forschung" wollte ich nichts beweisen und wollte keine revolutionären Schlussfolgerungen ziehen (und ich tat es nicht!). Ich wollte nur meine Neugier befriedigen, die Arbeit verschiedener Ansätze zur Lösung des klassischen Problems betrachten und meine Finger leicht strecken. Trotzdem hoffe ich, dass Sie auch neugierig waren, die Ergebnisse zu beobachten!