PHP-Skript: Größter gemeinsamer Teiler
Kann man eine ganze Zahl restlos durch eine andere ganze Zahl teilen, so heißt diese Zahl Teiler jener Zahl. Verschiedene Zahlen haben unter Umständen einige gleiche Teiler und der größte von ihnen, der sog. größte gemeinsame Teiler (kurz: ggT), ist für viele mathematische Fragestellungen interessant.
Wer nicht im Kopf sämtliche Teiler einer Zahl bilden will, kann den größten gemeinsamen Teiler auch mit Hilfe des fast 2500 Jahre alten euklidischen Algorithmus’ bestimmen, der allein mit einigen Subtraktionen auskommt. Bei weit auseinanderliegenden Zahlen kann dieser Algoritmus jedoch zu einer langwierigen Hin- und Herrechnerei ausarten. Eine verbesserte Version kürzt den Prozess daher mit Hilfe von einigen Divisionen ab.
Divisionen stellen jedoch für Computersysteme eine vergleichsweise aufwändige Rechenart dar. Daher basiert das nachfolgende Skript auf den für das Binärsystem optimierten steinschen Algorithmus. In den Erläuterungen finden Sie die Darstellung der Optimierungspunkte.
Austesten
Hier können Sie zunächst einmal die Funktion des Skriptes testen. Probieren Sie ruhig auch ein paar größere Zahlen, wobei Sie natürlich das obere Limit für Integer-Zahlen unter PHP im Blick haben sollten.
Syntax
int gcd (int $a, int $a)
- $a, $b - Je eine Ganzzahl, von denen der größte gemeinsame Teiler bestimmt werden soll.
Rückgabewerte: Es wird der größte gemeinsame Teiler als Ganzzahl zurückgegeben.
Skript
function gcd ($a, $b) {
$a = abs($a);
$b = abs($b);
$k = 0;
if (!($a && $b)) return 0;
if ($a == $b) return $a;
while (!($a & 1 || $b & 1)) {
$a = $a >> 1;
$b = $b >> 1;
$k++;
}
if ($a & 1) $d = -$b; else $d = $a;
while ($d) {
while (!($d & 1)) $d = $d >> 1;
if ($d > 0) $a = $d; else $b = -$d;
$d = $a - $b;
}
return $a << $k;
}
Erläuterungen
Zu Beginn stellen wir durch Anwenden der Betragsfunktion abs() sicher, dass beide Zahlen kein Vorzeichen aufweisen, da der größte gemeinsame Teiler nur für positive Ganzzahlen sinnvoll definiert ist. Wahlweise könnte man auch einen Fehler zurückgeben, anstatt das Vorzeichen einfach zu ignorieren.
Nun werden noch zwei Spezialfälle abgefangen. Während jede natürliche Zahl eine endliche Anzahl von Teilern aufweist, kann die Null durch jede beliebige Zahl geteilt werden, weil man stets wieder 0 als Ergebnis erhält. Es ist daher unsinnig einen größten gemeinsamen Teiler zu bestimmen, sobald eine Zahl 0 ist. Es hat sich eingebürgert in diesem Fall den unechten Teiler 0 als Ergebnis anzugeben, wenngleich man selbstverständlich auch einen Fehler zurückgeben kann. In PHP und vielen anderen Programmiersprachen ist die Frage jedoch im Prinzip überflüssig, da false intern ohnehin als 0 codiert wird. Weiterhin habe ich mich entschieden, den Fall abzufangen, dass beide Zahlen gleich sind. Zwar braucht das Skript hier keine besonders große Laufzeit, aber ich erachte es als unsinnig diesen trivialen Fall durch den Algorithmus laufen zu lassen, um eine einzige Programmzeile einzusparen.
Kommen wir zum eigentlichen Algorithmus. Wie oben schon erwähnt, ähnelt dieser von der Grundidee dem euklidischen Algorithmus, beginnt aber direkt mit einer Optimierung für das Binärsystem. Die erste While-Schleife wird zunächst solange durchlaufen, solange beide Zahlen gerade, also durch 2 teilbar sind. Ob eine Zahl ungerade ist, lässt sich mit binärer Logik leicht überprüfen: man muss lediglich schauen, ob das letzte Bit auf Eins gesetzt ist. Dies erreicht man durch eine binäre Und-Verknüpfung mit 1, welche eben nur dann 1 ergibt, wenn auch die Zahl selbst als letztes Bit eine Eins gesetzt hat. Die Negation ergibt dann entsprechend die Überprüfung auf eine gerade Zahl.
Wenn nun beide Zahlen durch 2 teilbar sind, merken wir uns dies in der Zählvariablen $k und teilen die beiden Zahlen sodann durch 2. Auch dies ist im Binärsystem ohne wesentlichen Aufwand möglich: dazu muss nur das letzte Bit gestrichen werden; man spricht auch von einer Verschiebung (Shift) nach rechts. Nach Abarbeitung der While-Schleife, gibt es nun keinen gemeinsamen Primfaktor 2 mehr. Gerade bei Zahlen, die den Primfaktor 2 sehr häufig enthalten, haben wir uns durch diesen Vorschritt eine Menge Laufzeit erspart.
In der nächsten und auch letzten While-Schleife wird dann der euklidische Algorithmus ausgeführt: es wird fortwährend der Abstand $d zwischen beiden Zahlen ermittelt und damit die größere Zahl ersetzt, bis der Abstand Null wird. Um uns die Abfrage nach der größeren Zahl zu ersparen, bilden wir einfach die vorzeichenbehaftete Differenz und entscheiden dann anhand des Vorzeichens. Auch dieser Schritt ist nocheinmal nach obigem Prinzip optimiert: Ist die Differenz gerade, so wird sie solange möglich, durch 2 geteilt. Dies können wir gefahrlos machen, da nach obigem Prozedere der Primfaktor 2 nicht mehr im ggT vorkommen kann.
Sobald nun der Abstand der Zahlen gleich Null ist, haben wir unseren ggT gefunden. Da jedoch im ersten Schritt bereits $k-mal der Primfaktor 2 extrahiert wurde, müssen wir den gefundenen ggT nun noch $k-mal mit 2 multiplizieren bzw. maschinenoptimiert $k Stellen nach links verschieben.