Barrett-Verfahren

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 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 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 <math>a</math> und <math>b</math> mit dem Barrett-Algorithmus läuft in drei Schritten ab. Im ersten Schritt wird mittels des Newton-Verfahrens 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 GMP zum Einsatz<ref>http://gmplib.org/manual/Block_002dWise-Barrett-Division.html</ref>.

Weblinks

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

Einzelnachweise