Steinscher Algorithmus
Der steinsche Algorithmus oder binäre euklidische Algorithmus dient der effizienten Berechnung des größten gemeinsamen Teilers. Der Algorithmus wurde 1967 vom Physiker Josef Stein (Hebräische Universität Jerusalem) vorgestellt.[1] Donald E. Knuth zufolge entwickelten R. Silver und J. Tersian den Algorithmus bereits 1962, publizierten ihn aber nicht.[2]
Der Algorithmus nutzt folgende Rechenregeln:
- , falls und gerade.
- , falls gerade und ungerade.
- , falls und ungerade.
Er ist auf Binärrechnern schneller als der jahrtausendealte euklidische Algorithmus, weil keine zeitaufwändigen Divisionen (bzw. Modulooperationen) durchgeführt werden müssen. Es sind nur Divisionen durch 2 erforderlich, wofür man nur das Bitmuster um eins nach rechts, zum niederwertigen Ende, schieben muss. Die meisten Prozessoren besitzen dafür ein effizientes Schieberegister.
Zu beachten ist, dass der steinsche Algorithmus nur dann richtig funktioniert, wenn vorzeichenlose Integer verwendet werden. Negative Zahlen müssen zuerst in positive überführt werden. Der euklidische Algorithmus hingegen funktioniert auch mit vorzeichenbehafteten Integertypen.
Prinzip
Zu bestimmen sei der größte gemeinsame Teiler der beiden positiven Zahlen und . Dazu wird als erstes eine Variable definiert und dieser wird der Wert 0 zugewiesen. Dann werden sowohl als auch solange durch 2 geteilt, bis und nicht mehr durch 2 teilbar sind. Bei jeder Halbierung wird um 1 erhöht.
Der zweite Teil benötigt eine zusätzliche Variable , der die Differenz von und zugewiesen wird. Jeder gemeinsame Teiler von und ist auch Teiler von , sodass gilt: . Die Variable wird anschließend noch, solange es sich um eine gerade Zahl handelt, durch 2 geteilt. Dann wird durch ersetzt und mit dem neuen ein neues berechnet. Der Algorithmus ist beendet, sobald gilt. Das Ergebnis ist dann .[3]
Algorithmus
Die hier in Pseudocode beschriebene Variante des Algorithmus entspricht im Wesentlichen derjenigen, die Donald E. Knuth in seinem Werk The Art of Computer Programming beschreibt.
STEIN(a,b) wenn a = 0 dann return b k 0 solange a und b gerade Zahlen sind a a/2 b b/2 k k + 1 wenn a eine ungerade Zahl ist dann t -b sonst t a solange t ≠ 0 solange t eine gerade Zahl ist t t/2 wenn t > 0 dann a t sonst b -t t a - b return a 2k
Viele Prozessoren haben heutzutage Befehlssätze, die sehr schnell (oft in einem Takt) bestimmen können, wie oft eine Ganzzahl durch Zwei teilbar ist. Zum Beispiel stellt die x86-Architektur seit dem 80386 für diesen Zweck die Instruktion bsf
zur Verfügung. Unter Verwendung einer solchen Instruktion ist es möglich, zwei der drei Schleifen des Algorithmus einzusparen und damit seine Laufzeit signifikant zu verbessern. Die folgende Implementierung in der Programmiersprache C nutzt zu diesem Zwecke die POSIX-Standardfunktion ffs
(find first set):
#include <stdlib.h> /* für abs() */
#include <strings.h> /* für ffs() */
int ggt(int a, int b)
{
register int c;
if ((a == 0) || (b == 0)) // falls eines oder beide Argumente 0 sind,
return a | b; // ist das andere Argument oder 0 das Ergebnis
// dies kann weggelassen werden, wenn a und b nicht negativ sein können
a = abs(a);
b = abs(b);
c = ffs(a | b) - 1;
a >>= ffs(a) - 1;
do {
b >>= ffs(b) - 1;
if (a > b) {
// vertausche Variablen, damit bei Subtraktion kein Überlauf stattfinden kann
int temp = b;
b = a;
a = temp;
}
b -= a;
} while (b != 0);
return a << c;
}
Eine Implementierung für vorzeichenlose Ganzzahlen in x86-Assembler, die bsf
nutzt:
ggt:
mov ecx, 4[esp] ; Lade a
mov eax, 8[esp] ; Lade b
test ecx, ecx ; Vergleiche a mit 0:
jz done ; falls a gleich 0 ist das Ergebnis b
cmp eax, ecx ; Vergleiche a mit b:
je done ; falls a gleich b ist das Ergebnis b
mov edx, eax ; Lade b
mov eax, ecx ; Lade a
test edx, edx ; Vergleiche b mit 0:
jz done ; falls b gleich 0 ist das Ergebnis a
push ebx
bsf ecx, edx ; Bestimme grösste Zweierpotenz von b
bsf ebx, eax ; Bestimme grösste Zweierpotenz von a
cmp ebx, ecx ; Vergleiche beide
cmova ebx, ecx ; und merke deren Minimum
shr edx, cl ; Dividiere b durch grösste Zweierpotenz
next:
bsf ecx, eax ; Bestimme grösste Zweierpotenz von a
shr eax, cl ; Dividiere a durch grösste Zweierpotenz
mov ecx, edx
cmp edx, eax ; Vergleiche b mit a
cmovb edx, eax ; und vertausche beide, falls b kleiner a
cmovb eax, ecx
sub edx, eax ; Subtrahiere a von b
jnz next ; und wiederhole, bis b gleich 0
mov ecx, ebx
shl eax, cl ; Multipliziere a mit 2**Minimum
pop ebx
done:
ret
Quellen
- ↑
- ↑ Donald E. Knuth: The Art of Computer Programming. Band 2: Seminumerical Algorithms. 3. Auflage. Addison-Wesley Professional, 1997, ISBN 0-201-89684-2, S. 338–341.
- ↑ Alexander Weers: Größter gemeinsamer Teiler. In: Formelsammlung24.de. Archiviert vom Original am 28. März 2018; abgerufen am 27. März 2018.