Barrett-Verfahren

Das Barrett-Verfahren ist ein Algorithmus zur effizienten Division großer Zahlen. Als Eingabe sind ganze Zahlen der Länge $m$ und $n$ mit $n\leq m\leq 2n$ erlaubt. Der Algorithmus funktioniert in jedem Zahlensystem; auf dem Rechner empfiehlt sich eine Zweierpotenz wie $2^{32}$ oder $2^{64}$ als Grundzahl. Zurückgeliefert wird außer dem Quotienten auch der 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 $a$ und $b$ mit dem Barrett-Algorithmus läuft in drei Schritten ab. Im ersten Schritt wird mittels des Newton-Verfahrens eine Näherung von ${\tfrac {2^{m}}{b}}$ berechnet ($m$ ist die Länge von $a$), wobei nur Multiplikationen, Additionen und Subtraktionen benötigt werden. Im zweiten Schritt wird der Näherungswert mit $a$ multipliziert, wodurch man eine Näherung von ${\tfrac {2^{m}\cdot a}{b}}$ erhält. Schließlich wird aus der Näherung der genaue Wert berechnet, wobei $O(1)$ Schritte genügen.

Erweiterung auf beliebige ganze Zahlen

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

Verwendung

Der Barrett-Algorithmus kommt in GMP zum Einsatz.

Weblinks

• Vergleich von Barrett- und Burnikel-Ziegler-Verfahren; enthält eine Beschreibung des Barrett-Verfahrens auf S. 17 (englisch) (PDF-Datei; 565 kB)