Steinscher Algorithmus

Der steinsche Algorithmus oder binäre euklidische Algorithmus dient der effizienten Berechnung des größten gemeinsamen Teilers. Der Algorithmus wurde 1967 von dem Deutschen Josef Stein vorgestellt. Es gibt Quellen, die behaupten, dass R. Silver und J. Tersian bereits 1962 den Algorithmus entwickelten.

Die Verbesserung gegenüber dem Jahrtausende alten Euklidischen Algorithmus resultiert aus der Ausnutzung folgender Rechenregeln:

• $\operatorname {ggT} (a,b)=2\operatorname {ggT} (a/2,b/2)$, falls a und b gerade.
• $\operatorname {ggT} (a,b)=\operatorname {ggT} (a/2,b)$, falls a gerade und b ungerade.
• $\operatorname {ggT} (a,b)=\operatorname {ggT} ((a-b)/2,b)$, falls a und b ungerade.

Einer der Vorteile dieses Algorithmus besteht darin, dass keine zeitaufwendigen Divisionen (bzw. Modulooperationen) durchgeführt werden müssen, sondern nur Divisionen durch 2 erforderlich sind, die auf Binärrechnern effizient ausgeführt werden können.

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)
 1  k $\leftarrow$ 0
 2  solange a und b gerade Zahlen sind
 3      a $\leftarrow$ a/2
 4      b $\leftarrow$ b/2
 5      k $\leftarrow$ k + 1
 6  wenn a eine ungerade Zahl ist
 7      dann t $\leftarrow$ -b
 8      sonst t $\leftarrow$ a
 9  solange t ≠ 0
10      solange t eine gerade Zahl ist
11          t $\leftarrow$ t/2
12      wenn t > 0
13          dann a $\leftarrow$ t
14          sonst b $\leftarrow$ -t
15      t $\leftarrow$ a - b
16  return $a\cdot 2^{k}$