Barrett-Verfahren

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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 | Quelltext 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.

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

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. http://gmplib.org/manual/Block_002dWise-Barrett-Division.html