Steinscher Algorithmus

Der steinsche Algorithmus oder binäre euklidische Algorithmus dient der effizienten Berechnung des größten gemeinsamen Teilers. Der Algorithmus wurde 1967 vom Deutschen Josef Stein vorgestellt. Donald Ervin Knuth zufolge entwickelten R. Silver und J. Tersian den Algorithmus bereits 1962, publizierten ihn aber nicht.

Der Algorithmus nutzt folgende 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.

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, für das man nur das Bitmuster um eins nach rechts, zum niederwertigen Ende, schieben muss. Die meisten Prozessoren besitzen dafür ein effizientes Schieberegister. Anmerkungen:

• Zu beachten ist, dass der steinsche Algorithmus nur dann richtig funktioniert, wenn vorzeichenbehaftete Integer verwendet werden. Der euklidische Algorithmus hingegen funktioniert auch mit vorzeichenlosen Integertypen.
• Der steinsche Algorithmus ist auf heutigen Rechnern nur dann effizienter, wenn der Integertyp nicht in ein Register hineinpasst, also mehrere Zugriffe pro Variable benötigt werden. Das ist beispielsweise bei 64-Bit Integerzahlen auf einem Rechner mit 32-Bit Registern der Fall. Umgekehrt ist der euklidische schneller, wenn der Integertyp vollständig in ein Register passt eine Variable also nur einen einzelnen Zugriff benötigt.

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 $\leftarrow$ 0
  solange a und b gerade Zahlen sind
      a $\leftarrow$ a/2
      b $\leftarrow$ b/2
      k $\leftarrow$ k + 1
  wenn a eine ungerade Zahl ist
      dann t $\leftarrow$ -b
      sonst t $\leftarrow$ a
  solange t ≠ 0
      solange t eine gerade Zahl ist
          t $\leftarrow$ t/2
      wenn t > 0
          dann a $\leftarrow$ t
          sonst b $\leftarrow$ -t
      t $\leftarrow$ a - b
  return a $\cdot$ 2k