Diskussion:Steinscher Algorithmus

Der Artikel ist meiner Meinung nach leider etwas kurz geraten. Für Außenstehende, die vom Steinschen Algorithmus noch nie etwas gehört haben, ihn aber trotzdem gerne anwenden würden fehlt ein wenig mehr erklärung. Wäre es vielleicht möglich ein Beispiel mit erklärung der Rechenschritte auf die Seite zu stellen?

Meiner Meinung nach vergessene Erklärungen

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.

Nur die Division durch 2 oder fehlt da (2 hoch k)?

Wie passiert das im binären Zahlensystem?

Warum ist das auf Binärrechnern effizent? 212.186.62.230 06:33, 25. Apr. 2009 (CEST) --

Der Artikel ist wirklich nicht für Leute ohne Fachwissen.

1. Division durch 2 ist durch den Algorithmus gegeben.

2. im binären Zahlensystem wird einfach nur die letzte Ziffer gestrichen (1001 : 10 => 100, funktioniert so auch im Dezimalsystem)

3. Das ist auf Binärrechnern (Rechnen mit der Basis 2) effizient, weil nur mit dem Operanden 2 gerechnet werden muß. So wie das Teilen durch 10 im Dezimalsystem sehr einfach ist (Streichen der letzten Stelle). Es muß nicht jede Ziffer der Zahl betrachtet werden.88.74.189.217 11:15, 16. Feb. 2012 (CET)

Ergänzung zu 2: Da nur (a-b) durch 2 geteilt wird, wenn a und b ungerade sind, ist (a-b) auch stets restlos durch zwei teilbar. Übertragen auf das Dezimalsystem: Wenn a und b die gleiche letzte Stelle haben, dann durch 10 teilen, also (666-336)/10 = 330/10 = 33. --Sepp (Diskussion) 13:49, 9. Mär. 2012 (CET)

Die Behauptungen

"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."

und

"Der steinsche Algorithmus ist auf heutigen Rechnern nur dann effizienter, wenn der Integertyp nicht in ein Register hineinpasst, beispielsweise bei 64-Bit Integerzahlen auf einem Rechner mit 32-Bit Registern. Umgekehrt ist der euklidische schneller, wenn der Integertyp vollständig in ein Register passt."

sind falsch. -- 79.199.160.159 09:35, 16. Mai 2012 (CEST)

Das mit dem unsigned/signed Integer wurde, denke ich, einfach vertauscht. Wenn es beim Shiften Probleme gibt, dann doch höchstens durch das Vorzeichen. Gibt es kein Vorzeichen funktioniert doch alles, wie es soll. (nicht signierter Beitrag von 84.59.98.230 (Diskussion) 16:58, 5. Aug. 2013 (CEST))

Division durch Zwei ist auf Binärrechnern eine Shift-Operation. Je nach Architektur kann diese schneller erfolgen als eine "echte" Division: Sie kann aber auf jeden Fall mit geringerem Hardware-Aufwand realisiert werden. --XXLRay (Diskussion) 10:34, 6. Aug. 2013 (CEST)

Boa, echt, ey

Der Ansicht, dieser Artikel sei nur etwas für Leute mit Fachwissen muß ich energisch widersprechen. Nur naive Jungpennäler werden mit diesen Ausführungen zB ggT(10, 25) lösen können. Wer mehr weiß und versteht, schlägt die Hände über dem Kopf zusammen. Beinahe alle Aussagen oder Sätze sind falsch, mißverständlich, bedenklich oder nur eingeschränkt richtig. Im Einzelnen:

• Der Steinsche Algorithmus ist eben kein "binärer Euklidscher Algorithmus", er hat damit überhaupt nichts zu tun. Da verwechselt jemand den Euklidschen Algorithmus synonym mit GgT-Suche. Siehe englisch "Binary GCD-Algorithm". Der Steinsche und der Euklidischen Algorithmus haben zwar die Subtraktion gemeinsam, aber es führt nicht weiter, aus dieser eher konstruierten Parallelen eine Verwandschaft herzuleiten.
• Ob er der "effizienten Berechnung dient" ist Ansichtsache und von vielen Umständen abhängig.
• Josef Stein war ein israelischer Mathematiker, der um 1930 in Palestina geboren wurde. Bei der Abgabe des Manuskripts 1966 war er Professor an der hebräischen Universität in Jerusalem.
• Die "Rechenregeln" führen nur dann zum richtigen Ergebnis, wenn a und b positiv sind, die Rekursionsfunktion ggT(a, b) als ersten Parameter aber auch negative Werte akzeptiert. Für zwei negative Werte terminiert der Algorithmus zwar auch, aber mit dem falschen Ergebnis. Haben a und b verschiedene Vorzeichen wird die Rekursion endlos, zB ggT(-1, 1). Außerdem fehlt die Terminierungsbedingung: wenn a=b oder a=0 return b.

Der Rest bis zum Abschnitt "Algorithmus" ist kompletter Quatsch. Zunachst müßte geklärt werden, welcher Euklidische Algorithmus gemeint ist, der mit Subtraktion oder der mit Modulo, beide sind gleichermaßen über 2000 Jahre alt, zu Euklids Zeit wurde aber nur die Subtraktionsversion mit geometrischen Methoden bewiesen. Welche "meisten Prozessoren" haben eigentlich "ein effizientes Schieberegister"? Ich kenne keinen! Keinen Z80, Intel 80x8x, Pentium, Motorola 68k oder PowerPC Siemens 8015++... Alle unterstützen Schieben im Akkumulator oder den Universalregistern. Schieben kann auch nur für positive Zahlen die Division durch 2 ersetzen. Der angegebene Pseudocode funktioniert also nicht mit Schieben, weil die Hilfszahl t negativ werden darf und soll. Der Pseudocode ist aber ohnehin nicht besonders praktikabel, zur Demonstration (Knuth) oder für Pennäler reicht es aber.

Der Steinsche Algorithmus ist in jedem mathematischen oder Zahlensystem vorteilhaft, in dem eine Subtraktion und eine Division durch 2 deutlich schneller sind, als eine Modulooperation mit großen Zahlen. Das gilt zB sehr anschaulich für handschriftliche Rechnung im Dezimalsystem. Auf automatischen Rechenmaschinen muß zusätzlich sicher sein, daß die zusätzlichen Abfragen (gerade, Vorzeichen, Vergleich) und die Subtraktion nicht zu aufwendig sind. Außerdem muß die Programmiersprache die schnelle Division durch 2 oder binäres Schieben unterstützen.

Die Anmerkungen:

• Ob der verwendete Datentyp negative Zahlen darstellen kann oder nicht ist für beide Algorithem unerheblich, es sei denn, man programmiert sie so, daß es eine Rolle spielt, wie im Pseudocode. Beide oder alle drei Algorithmen liefern nur für positive Zahlen sinnvolle Ergebnisse.
• Der Effizienzvergleich zwischen den Algorithmen hat nichts mit Registern und Integern zu tun, sondern ausschließlich mit der Effizienz der verwendeten Rechenoperationen. Wenn die Division durch 2 nicht wesentlich schneller ist als die allgemeine Division, nützt der Steinsche Algorithmus auch nichts. Eventuelll sind ja auch die Vergleiche oder die Subtraktion teuer.

PositiverInt ggTStein(PositiverInt a, PositiverInt b)
    {
    if      (a == 0)           return  b;	// triviale Lösung
    else if (b == 0)           return  a;	// triviale Lösung
    else if (a == b)           return  b;	// normales Rekursionsende
    else if ((a mod 2) == 0)
         if ((b mod 2) == 0)   return  ggTStein( a/2,  b/2) * 2;
         else                  return  ggTStein( a/2,  b  );
    else if ((b mod 2) == 0)   return  ggTStein( b/2,  a  );
    else if (a < b)            return  ggTStein((b-a)/2, a);
         else                  return  ggTStein((a-b)/2, b);
    }

Ich vermisse auch die Erweiterung nach Richard Brent und H.T. Kung mit einer Division durch 4. Diese lohnt sich, wenn man sehr preiswert (a mod 4) und (b mod 4) zB durch maskieren des niederwertigisten Byte ermitteln kann.

PositiverInt ggTBrentKung(PositiverInt a, PositiverInt b)
    {
    if      (a == 0)                  return  b;	// triviale Lösung
    else if (b == 0)                  return  a;	// triviale Lösung
    else if (a == b)                  return  b;	// normales Rekursionsende
    else if ((a mod 2) == 0)
         if ((b mod 2) == 0)          return  ggTBrentKung( a/2,  b/2) * 2;
         else                         return  ggTBrentKung( a/2,  b  );
    else if ((b mod 2) == 0)          return  ggTBrentKung( b/2,  a  );
    else if ((a mod 4) == (b mod 4))
         if (a < b)                   return  ggTBrentKung((b-a)/4, a);
         else                         return  ggTBrentKung((a-b)/4, b);
    else if (a < b)                   return  ggTBrentKung((a+b)/4, a);
         else                         return  ggTBrentKung((a+b)/4, b);
    // Für einen günstigeren Worst Case können die letzten beiden Zeilen
    //  durch den Steinschen Algorithmus ersetzt werden, muss aber nicht
//  else if (a < b)                   return  ggTBrentKung((b-a)/2, a);
//       else                         return  ggTBrentKung((a-b)/2, b);
    }

Rekursive Lösungen sehen zwar oft elegant aus, sind aber selten schnell, resourcenschonend oder efizient. Man wird diese Codebeispiele also kaum für die Untersuchung von Zahlen mit vielen Millionen Stellen verwenden, da die Rekursionstiefe linear von der Stellenzahl abhängt. Für diese Aufgaben sind aber die Algorithmen von Stein oder Brent/Kung besonders interessant.--46.115.140.103 10:40, 24. Jan. 2014 (CET)

-- 46.115.140.103, das kann ich nicht so stehen lassen. Der Steinsche Algorithmus ist nichts als ein schlau optimierter klassischer euklidscher Algorithmus. Beide beruhen auf der Regel, dass aus "ca proportional zu cb" folgt, dass ca-cb weil gleich c(a-b) proportional zu cb (und auch ca) ist und natürlich, dass die Differenzen immer kleiner werden, d.h der Algorithmus korrekt terminiert (was sich leicht beweisen lässt). Im Grunde gilt das auch für den modernen euklidschen Algorithmus, wo mur die Mehrfachsubtraktion durch modulo ersetzt ist.

Die Optimierung Steins besteht aus den drei Rechenregeln des Artikels. Die dritte Regel das "wechelseitige Abziehen" Euklids zusammen mit der Erkenntnis, dass die Differenz zweier ungerader Zahlen gerade ist, mithin Regel 2 angewand werden kann.

Ich sehe also nicht, wo so am Artikel gemeckert werden kann.

(jb) --5.145.140.194 16:52, 24. Jan. 2014 (CET)

Geschwindigkeit

Folgender Abschnitt ist falsch:

• 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.

Es kostet zwar nur eine Instruktion, diese Instruktion kostet aber viele Zyklen. Moderne CPUs haben eine Instruktion zum Zählen von Nullen am Ende einer Zahl. Diese Instruktion ist sehr schnell, Bitverschiebungen ebenso. Eigene Implementationen zeigen Geschwindigkeitserhöhungen von 40% - 200% (je nach Integervariablengröße). Dieser Blogpost zeigt ebenfalls deutliche Verbesserungen und auch die hochoptimierte GMP-Bibliothek für beliebig große Ganzzahlen nutzt den Steinschen Algorithmus (allerdings nur für kleine Bigints) Beweis.

Die Aussage ist also falsch herum. Wenn Integertypen in ein Register passen ist Stein schneller. Euklid ist nur dann schneller, wenn Division schneller ist als Nullenzählen und Bitverschieben. Das ist architekturabhängig, sollte aber nur selten der Fall sein. Bei großen Zahlen gibt es asymptotisch bessere Algorithmen. --134.130.4.241 18:00, 7. Sep. 2015 (CEST)

Josef Stein

Es gab hier Unstimmigkeiten, ob er Deutscher oder Israeli ist. Das einzige, was sich mit den angegebenen Quellen belegen läßt, ist seine damalige Tätigkeit an der Hebrew University, weshalb ich die Angabe Deutscher/Israeli durch diese Angabe ersetzen werde.—Hoegiro (Diskussion) 18:34, 29. Okt. 2020 (CET)