Das Kefk Network Wiki befindet sich im Testbetrieb.

Aus Kefk.

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 and J. Tersian bereits 1962 den Algorithmus entwickelten.

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

• , falls a und b gerade.
• , falls a gerade und b ungerade.
• , falls a und b ungerade.

Einer der Vorteile dieses Algorithmus besteht darin, dass keine zeitaufwendigen Divisionen durchgeführt werden müssen.

Algorithmus

Der hier in Pseudocode beschriebene Variante des Algorithmus entspricht im Wesentlichen derjenigen, die Donald E. Knuth in seinem Werk The Art of Computer Programming beschrieb.^[1]

STEIN(a,b)
 1  k  0
 2  solange a und b gerade Zahlen sind
 3      a  a/2
 4      b  b/2
 5      k  k + 1
 6  wenn a eine ungerade Zahl ist
 7      dann t  -b
 8      sonst t  a
 9  solange t ≠ 0
10      solange t eine gerade Zahl ist
11          t  t/2
12      wenn t > 0
13          dann a  t
14          sonst b  -t
15      t  a - b
16  return 

Quellen

1. ↑ 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

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Steinscher_Algorithmus, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.