| dbo:abstract
|
- 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:
* , falls a und b gerade.
* , falls a gerade und b ungerade.
* , 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. (de)
- 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:
* , falls a und b gerade.
* , falls a gerade und b ungerade.
* , 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. (de)
|
| rdfs:comment
|
- 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:
* , falls a und b gerade.
* , falls a gerade und b ungerade.
* , falls a und b ungerade. (de)
- 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:
* , falls a und b gerade.
* , falls a gerade und b ungerade.
* , falls a und b ungerade. (de)
|
