PHP-Skript: Größter gemeinsamer Teiler
Dieses Tutorial zeigt, wie man den größten gemeinsamen Teiler zweier Zahlen mit PHP besonders performant bestimmt.
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 sogenannte 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 dem für das Binärsystem optimierten steinschen Algorithmus. In den Erläuterungen finden Sie die Darstellung der Optimierungspunkte.
Anwendungsbeispiel
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.
Liegen die zwei Zahlen in den Variablen $lNumber1 und $lNumber2 vor, so sähe ein möglicher Aufruf der Funktion wie folgt aus:
echo 'Der größte gemeinsame Teiler von ' . $lNumber1 . ' und ' .
$lNumber2 . ' ist ' . gcd($lNumber1, $lNumber2) . '.';
Syntax
int gcd (int $pNumber1, int $pNumber2)
$pNumber1
Die erste ganze Zahl, von der der größte gemeinsamer Teiler bestimmt werden soll.
$pNumber2
Die zweite ganze Zahl, von der der größte gemeinsamer Teiler bestimmt werden soll.
Kommentiertes Skript
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. Außerdem intialisieren wir noch die lokale Variable $lShiftCount, die später noch näher erläutert wird.
function gcd ($pNumber1, $pNumber2)
{
$lNumber1 = abs($pNumber1);
$lNumber2 = abs($pNumber2);
$lShiftCount = 0;
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.
Um die Abfrage, ob eine der Zahlen (oder auch beide) 0 ist, möglichst performant durchzuführen, werden die beiden Zahlen logisch mit UND verknüft. Genau dann, wenn mindestens eine Zahl 0 ist, also als Bitmuster gesehen ausschließlich Nullen enthält, ist auch das Ergebnis 0, was logisch false entspricht. Durch Negation erhalten wird die passende Bedingung.
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 Anweisung einzusparen.
if (!($lNumber1 && $lNumber2)) {
return 0;
}
if ($lNumber1 == $lNumber2) {
return $lNumber1;
}
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 $lShiftCount 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. Bei Zahlen, die den Primfaktor 2 sehr häufig enthalten, haben wir uns durch diese Vorarbeit eine Menge Laufzeit erspart.
while (!($lNumber1 & 1 || $lNumber2 & 1)) {
$lNumber1 = $lNumber1 >> 1;
$lNumber2 = $lNumber2 >> 1;
$lShiftCount++;
}
In der nächsten und auch letzten While-Schleife wird dann der euklidische Algorithmus ausgeführt: es wird fortwährend der Abstand $lDistance zwischen beiden Zahlen ermittelt und damit die größere Zahl ersetzt, bis der Abstand 0 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.
if ($lNumber1 & 1) {
$lDistance = -$lNumber2;
} else {
$lDistance = $lNumber1;
}
while ($lDistance) {
while (!($lDistance & 1)) {
$lDistance = $lDistance >> 1;
}
if ($lDistance > 0) {
$lNumber1 = $lDistance;
} else {
$lNumber2 = -$lDistance;
}
$lDistance = $lNumber1 - $lNumber2;
}
Sobald nun der Abstand der Zahlen gleich 0 ist, haben wir unseren ggT gefunden. Da jedoch im ersten Schritt bereits $lShiftCount-mal der Primfaktor 2 extrahiert wurde, müssen wir den gefundenen ggT nun noch $lShiftCount-mal mit 2 multiplizieren bzw. maschinenoptimiert die Bits um $lShiftCount Stellen nach links verschieben.
return $lNumber1 << $lShiftCount;
}
Skript zum Herunterladen
Das Skript ist in einer Textdatei mit der Kodierung UTF-8 hinterlegt, damit es nicht vom PHP-Interpreter auf meinem Webspace ausgeführt wird und Sie es herunterladen können. Sie können den benötigten Programmcode entweder in Ihr Skript hinüberkopieren oder aber das Skript speichern und die Endung auf .php ändern.