Das Barrett-Verfahren ist ein Algorithmus zur effizienten Division großer Zahlen. Als Eingabe sind ganze Zahlen der Länge und mit erlaubt. Der Algorithmus funktioniert in jedem Zahlensystem; auf dem Rechner empfiehlt sich eine Zweierpotenz wie oder 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   und   mit dem Barrett-Algorithmus läuft in drei Schritten ab. Im ersten Schritt wird mittels des Newton-Verfahrens eine Näherung von   berechnet (  ist die Länge von  ), wobei nur Multiplikationen, Additionen und Subtraktionen benötigt werden. Im zweiten Schritt wird der Näherungswert mit   multipliziert, wodurch man eine Näherung von   erhält. Schließlich wird aus der Näherung der genaue Wert berechnet, wobei   Schritte genügen.

Erweiterung auf beliebige ganze Zahlen

Bearbeiten

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

Verwendung

Bearbeiten

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

Bearbeiten

Einzelnachweise

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