Steinscher Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.[1] Donald Ervin Knuth zufolge entwickelten R. Silver und J. Tersian den Algorithmus bereits 1962, publizierten ihn aber nicht.[2]

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[Bearbeiten]

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

Quellen[Bearbeiten]

  1. J. Stein: Computational problems associated with Racah algebra. Journal of Computational Physics, Vol. 1, No. 3, pp. 397–405, 1967, ISSN 0021-9991, doi:10.1016/0021-9991(67)90047-2.
  2. Donald E. Knuth: The Art of Computer Programming. Volume 2: Seminumerical Algorithms. 3. Auflage. Addison-Wesley Professional, 1997, ISBN 0-201-89684-2, S. 338–341