imported>UncleOwen: Leerzeichen in Links entfern

2026-01-01T17:39:54Z

Leerzeichen in Links entfern

Neue Seite

Das '''Barrett-Verfahren''' ist ein Algorithmus zur effizienten Division großer Zahlen. Als Eingabe sind ganze Zahlen der Länge <math>m</math> und <math>n</math> mit <math>n \le m\le 2n</math> erlaubt. Der Algorithmus funktioniert in jedem [[Stellenwertsystem | Zahlensystem]]; auf dem Rechner empfiehlt sich eine Zweierpotenz wie <math>2^{32}</math> oder <math>2^{64}</math> als Grundzahl.
Zurückgeliefert wird außer dem [[Quotient | Quotienten]] auch der [[Division mit Rest | Rest]].

Das Barrett-Verfahren lohnt sich erst ab ca. 1,5 Millionen Dezimalstellen; darunter ist das [[Burnikel-Ziegler-Verfahren]] schneller. Bei genügend vielen Divisionen durch die gleiche Zahl ist das Barrett-Verfahren allerdings im Vorteil, da der Reziprokwert wiederverwendet werden kann.

== Beschreibung ==
Die Division zweier Zahlen <math>a</math> und <math>b</math> mit dem Barrett-Algorithmus läuft in drei Schritten ab. Im ersten Schritt wird mittels des [[Newton-Verfahren]]s eine Näherung von <math>\tfrac{2^m}{b}</math> berechnet (<math>m</math> ist die Länge von <math>a</math>), wobei nur Multiplikationen, Additionen und Subtraktionen benötigt werden.
Im zweiten Schritt wird der Näherungswert mit <math>a</math> multipliziert, wodurch man eine Näherung von <math>\tfrac{2^m \cdot a}{b}</math> erhält. Schließlich wird aus der Näherung der genaue Wert berechnet, wobei <math>O(1)</math> Schritte genügen.

== Erweiterung auf beliebige ganze Zahlen ==
Erfüllen die Ausgangswerte <math>a</math> und <math>b</math> die Bedingung <math>n \le m\le 2n</math> nicht (d. h. ist <math>a</math> mehr als doppelt so lang wie <math>b</math>), so teilt man <math>a</math> in Abschnitte der Länge <math>\le n</math> auf und behandelt jeden Abschnitt als eine Ziffer. Man dividiert dann die Zahl <math>a</math> nach der Schulmethode durch <math>b</math>, wobei die einzelnen „Ziffern“ mit dem Barrett-Verfahren dividiert werden. Dies lässt sich effizient durchführen, weil man den (binär verschobenen) Reziprokwert <math>\tfrac{2^m}{b}</math> nur einmal berechnen muss und der Divisor <math>b</math> nur eine „Ziffer“ (der Länge <math>n</math>) hat.

== Verwendung ==
Der Barrett-Algorithmus kommt in [[GNU Multiple Precision Arithmetic Library | GMP]] zum Einsatz<ref>http://gmplib.org/manual/Block_002dWise-Barrett-Division.html</ref>.

== Weblinks ==
* [http://treskal.com/kalle/exjobb/original-report.pdf Vergleich von Barrett- und Burnikel-Ziegler-Verfahren; enthält eine Beschreibung des Barrett-Verfahrens auf S. 17 (englisch)] (PDF-Datei; 565 kB)

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus]]
[[Kategorie:Division (Mathematik)]]

Barrett-Verfahren - Versionsgeschichte

imported>UncleOwen: Leerzeichen in Links entfern