Steinscher Algorithmus - LinkFang.de





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.[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:

  • [math]\operatorname{ggT}(a, b) = 2 \operatorname{ggT}(a/2, b/2)[/math], falls a und b gerade.
  • [math]\operatorname{ggT}(a, b) = \operatorname{ggT}(a/2, b)[/math], falls a gerade und b ungerade.
  • [math]\operatorname{ggT}(a, b) = \operatorname{ggT}((a-b)/2,b)[/math], 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 vorzeichenlose Integer verwendet werden. Negative Zahlen müssen zuerst in positive überführt werden. Der euklidische Algorithmus hingegen funktioniert auch mit vorzeichenbehafteten Integertypen.

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 [math]\leftarrow[/math] 0
  solange a und b gerade Zahlen sind
      a [math]\leftarrow[/math] a/2
      b [math]\leftarrow[/math] b/2
      k [math]\leftarrow[/math] k + 1
  wenn a eine ungerade Zahl ist
      dann t [math]\leftarrow[/math] -b
      sonst t [math]\leftarrow[/math] a
  solange t ≠ 0
      solange t eine gerade Zahl ist
          t [math]\leftarrow[/math] t/2
      wenn t > 0
          dann a [math]\leftarrow[/math] t
          sonst b [math]\leftarrow[/math] -t
      t [math]\leftarrow[/math] a - b
  return a [math] \cdot [/math] 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() */
 
extern int
ggt(int a, int b)
{
    register int k;
 
    if (a == 0 || b == 0)
        return a | b;
 
    /* dies kann weggelassen werden, wenn a und b nicht negativ sein dürfen */
    a = abs(a);
    b = abs(b);
 
    k = ffs(a | b) - 1;
    a >>= ffs(a) - 1;
    b >>= ffs(b) - 1; // diese Zeile kann weggelassen werden, geschieht auch in Schleife
 
    while (b != 0) {
        b >>= ffs(b) - 1;
        if (a > b) {
            // vertausche Variablen, damit kein Überlauf bei Subtraktion stattfinden kann
            int temp = b;
            b = a;
            a = temp;
        }
 
        b -= a;
    };
 
    return a << k;
}

Quellen

  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

Kategorien: Zahlentheoretischer Algorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Steinscher Algorithmus (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.