Barrett-Verfahren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 \le m\le 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[Bearbeiten]

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[Bearbeiten]

Erfüllen die Ausgangswerte a und b die Bedingung n \le m\le 2n nicht (d.h. ist a mehr als doppelt so lang wie b), so teilt man a in Abschnitte der Länge \le 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[Bearbeiten]

Der Barrett-Algorithmus kommt in GMP zum Einsatz [1].

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. http://gmplib.org/manual/Block_002dWise-Barrett-Division.html