Kürzen eines Bruches - der Euklidische AlgorithmusIn diesem zweiten kleinen Beispiel soll es um die Analyse des Euklidischen Algorithmus gehen. Mir ist bewusst, dass dieser in vielen Büchern über Programmierung kurz vorgestellt wird, ausführlich beschrieben wird er hingegen kaum und dies ist das Manko, welches ich mit diesem Text beseitigen will. Doch auch hier geht es mir weniger um den Algorithmus als um Methoden, wie man ihn verbessern kann. Im Laufe des Textes wird sich zeigen, dass schon eine einzelne Rechenoperation jede Menge Rechenzeit sparen kann, was bei größeren Algorithmen unabdingbar ist... Der "klassische" Euklidische AlgorithmusEin klassisches Problem der Mathematik ist das Kürzen eines Bruches auf seine reduzierte Form. Bei näherer Betrachtung ist die Lösung dafür gleichbedeutend mit dem Finden des größten gemeinsamen Teilers (ggT) von Zähler und Nenner, durch welchen diese dann dividiert werden müssen, um den "gekürzten" Bruch zu erhalten.Schon vor über 2000 Jahren wurde im alten Griechenland durch Euklid ein Weg gefunden, wie man den ggT zweier Zahlen errechnen kann. Dieses Verfahren beschrieb Euklid ausführlich in seinem Werk "Elemente" und ist uns heute in der Informatik als Euklidischer Algorithmus bekannt. Dieser beruht auf folgender Tatsache: Es seien zwei Zahlen u und v gegeben. Wenn u>v, dann ist der ggT von u und v gleich dem ggT von v und u-v. Dieser Satz wird solange angewandt, bis u=0 ist. Ggf. müssen u und v vertauscht werden, sodass u immer größer als v ist und o.a. Satz Gültigkeit behält. Folgender Codeteil realisiert den "klassischen" Euklidischen Algorithmus in C:
void tausche(int *zahl1, int *zahl2){
int hilf=*zahl1;
*zahl1=*zahl2;
*zahl2=hilf;
}
int ggt(int u, int v){
while(u>0){
if(u<v)
tausche(&u, &v);
u=u-v;
}
return v;
}
Zu sehen ist zunächst die while-Schleife, welche solange durchlaufen wird, bis u den Wert 0 annimmt. Um die Aussage "wenn u größer v" gerecht zu werden und somit die Subtraktion durchführen zu können, müssen u und v eventuell vertauscht werden, womit garantiert wird, dass u größer v ist. Diese Abfrage geschieht mit der if-Anweisung, welche die Funktion tausche() aufruft, um beide Zahlen miteinander zu vertauschen. Als letzte Schleifenanweisung wird "u=u-v", was bedeutet, dass beim nächsten Schleifenaufruf der ggT von v und u-v ermittelt wird. Nimmt u den Wert 0 (oder kleiner) an, so bricht die Schleife ab und der ggT von u und v ist ermittelt: er ist gleich dem zuletzt berechneten v. Dieser Wert wird schlussendlich zurück gegeben. Verbesserungswürdig...Die Laufzeiteigenschaften des klassischen Algorithmus kann man am besten an einem Beispiel verdeutlichen:Gesucht wird der ggT der Zahlen 64 und 124. Folgende Werte nehmen u und v für dieses Beispiel jeweils an: (u,v)=(64,124) (60,64) (4,60) (56,4) (52,4) (48,4) (44,4) (40,4)
(36,4) (32,4) (28,4) (24,4) (20,4) (16,4) (12,4) (8,4) (4,4)Es ist deutlich erkennbar, dass v nach dem 3. Schleifendurchlauf immer den Wert 4 annimmt, welches auch den ggT beider Zahlen darstellt. Man könnte jetzt in Versuchung kommen zu sagen, dass mit der Schleife abgebrochen werden kann, sobald sich v nicht mehr ändert, dies ist aber falsch, da sich die 4 z.B. auch noch in eine 2 oder 1 ändern könnte, wenn u<v wird. Noch viel schlechter verhält sich der Algorithmus, wenn eine der beiden Zahlen sehr klein ist, z.B. 1: sind die Zahlen 12345 und 1 gegeben, so würde die o.a. Funktion ggt() 12345-mal die while-Schleife durchlaufen, da von der großen Zahl pro Schleifenaufruf nur 1 subtrahiert wird. Was dies für enorm große Zahlen bedeutet, kann man sich ja vorstellen... Der verbesserte AlgorithmusBei näherer Betrachtung stellt sich heraus, dass der Algorithmus solange v von u subtrahiert, bis u einen Wert erhält, der kleiner als v ist. Schaut man genauer hin, so ist dieser Wert gleich dem Rest, der bei der Division von u durch v übrig bleibt. Soll heißen: durch u%v (modulo-Operator: ermittelt den Rest einer ganzzahligen Division) lassen sich alle doppelten v's eliminieren. Probieren wir's aus! Folgender Code-Teil realisiert die modulo-Version, wobei Beachtung finden muss, dass der Vergleich "u<v" weg gelassen wurde. Grund: dem %-Operator kann es egal sein, ob u kleiner v ist oder nicht, da dies nur bei der mehrfachen Subtraktion "u-v" relevant ist. Da der %-Operator mit Resten arbeitet, kommt man im Endeffekt auf dasselbe Ergebnis. Dieses Weglassen der if-Anweisung impliziert natürlich auch ein Weglassen der tausche()-Funktion. Dieses Tauschen geschieht jetzt in Verbindung mit der Wertezuweisung für den nächsten Schleifendurchlauf:
int ggt_mod(int u, int v){
int hilf;
while(u>0){
hilf=u;
u=v%u;
v=hilf;
}
return v;
}Der einzige Unterschied zur obigen "klassischen" Variante des Euklidischen Algorithmus besteht also in der Ersetzung der Subtraktion durch die modulo-Operation. Dass man hier ganz gewaltig von "kleine Ursache, große Wirkung" sprechen kann, zeigt der Ablauf des Algorithmus für die schon oben verwendeten Zahlen 64 und 124: (u,v)=(64,124) (60,64) (4,60) Statt 17 Schleifendurchläufe benötigt der neue Algorithmus also nur noch 3! Wenn das keine Verbesserung ist?! Die Ursache dafür ist ganz klar: statt immer wieder dieselbe Zahl zu subtrahieren, wird einfach das entsprechende Vielfache von v quasi "subtrahiert", indem man den ganzzahligen Divisionsrest ermittelt. Weiters hatte ich oben schon einmal die beiden Zahlen 12345 und 1 angeführt. Der "klassische" Algorithmus benötigt 12345 Schleifendurchläufe. Und wie sieht es mit dem neuen aus? EINEN ganzen Durchlauf benötigt er (dann Abbruch, da 12345%1=0)! Im Allgemeinen lässt sich sagen, dass die %-Operation zwar mehr Rechenzeit in Anspruch nimmt als eine einfache Subtraktion, dies aber durch die enorme Einsparung an Schleifendurchläufen mehr als wett gemacht wird. Das Ganze noch rekursivSchön übersichtlich lassen sich beide Algorithmenvarianten natürlich auch durch rekursive Funktionsaufrufe darstellen, welche zwar einen gewissen Overhead erzeugen (durch die fortlaufenden Variablendeklarationen), dafür aber auch das Tauschen von u und v gleich mit im rekursiven Funktionsaufruf enthalten. Vor allem bei der %-Version macht sich die Rekursion positiv auf den Gesamteindruck bemerkbar:
int ggt_rek(int u, int v){
if(u>0)
if(u<v)
return ggt_rek(v-u, u);
else
return ggt_rek(u-v, v);
else
return v;
}
int ggt_mod_rek(int u, int v){
if(u>0)
return ggt_mod_rek(v%u, u);
else
return v;
}Mithilfe von bedingten Anweisungen lassen sich diese rekursiven Funktionen noch weiter komprimieren. Man mag nicht glauben, welche Konstruktionen doch mit C möglich sind ;-) :
int ggt_rek2(int u, int v){
return ((u>0) ? ((u<v) ? ggt_rek2(v-u, u) : ggt_rek2(u-v, v)) : v);
}
int ggt_mod_rek2(int u, int v){
return ((u>0) ? ggt_mod_rek2(v%u, u) : v);
}Der klassische und verbesserte Algorithmus sowie die rekursiven Versionen habe ich in einem kleinen Programm untergebracht. Dieses durchläuft alle Varianten mit einem vom Benutzer eingegebenem Bruch und gibt die Anzahl der Schleifendurchläufe bzw. der Rekursionsaufrufe aus. Kompiliert man das Programm zusätzlich mit gcc -DTEST -o euklid euklid.c, so gibt es
die jeweiligen Wertepaare für u und v aus, solange die Schleife durchlaufen wird bzw. die Rekursion stattfindet.
Zum Abschluss bleibt mir nur noch zu sagen, dass in diesem Text der Schwerpunkt darauf lag zu zeigen, dass kleine Dinge manchmal eine große Wirkung haben und dass dieser Satz besonders in der Algorithmik gilt. Eine Lösung für ein Problem zu finden ist die eine Sache, eine elegante und schnelle Lösung zu finden hingegen die andere. Ich hoffe, auch dieser Text konnte ein wenig sensibilisieren für durchdachte Algorithmenkonstruktion und nebenbei auch die Rekursion und natürlich den Euklidischen Algorithmus verständnisvoll herüberbringen. Für Sorgen, Nöte und Anträge stehe ich natürlich wie immer zur Verfügung ;) (c) 2003 by RTC, www.linux-related.de
|