Burnikel-Ziegler-Verfahren

Das Burnikel-Ziegler-Verfahren ist ein 1998 von Christoph Burnikel und Joachim Ziegler beschriebener Divisions-Algorithmus für ganze Zahlen. Er berechnet außer dem Quotienten auch den Rest.

Die Laufzeitkomplexität hängt vom eingesetzten Multiplikationsalgorithmus ab. Wenn die Multiplikation $O(n^{c})$ Schritte benötigt, wie es beim Karazuba- und dem Toom-Cook-Algorithmus der Fall ist, läuft die Burnikel-Ziegler-Division ebenfalls in $O(n^{c})$ Schritten ab. Liegt die Multiplikationskomplexität bei $O(n\cdot \log(n)\cdot \log(\log n))$, was dem Schönhage-Strassen-Algorithmus entspricht, so verringert sich die Komplexität der Division auf $O(n\cdot \log ^{2}(n)\cdot \log(\log n))$.

In der Praxis ist der Burnikel-Ziegler-Algorithmus zwischen ca. 250 und 1,5 Millionen Dezimalstellen schneller als die Schulmethode und das Barrett-Verfahren.

Beschreibung

Kernstück des Algorithmus sind zwei Unteralgorithmen namens $D_{2n/1n}$ und $D_{3n/2n}$, die Zahlen der Länge $2n$ und $1n$ bzw. $3n$ und $2n$ dividieren und sich gegenseitig rekursiv aufrufen. Bei jedem Aufruf verkürzt sich die Zahlenlänge um 1/4 bzw. 1/3; es kommen dabei Additionen, Subtraktionen, Verschiebungen und Elementardivisionen zum Einsatz. Der Unteralgorithmus $D_{3n/2n}$ führt darüber hinaus eine Multiplikation durch und profitiert von schnellen Multiplikationsalgorithmen (s. o.).

Dritter Bestandteil ist ein Algorithmus namens $D_{r/s}$, der die Ausgangszahlen so aufteilt, dass sie für $D_{2n/1n}$ geeignet sind.

Verwendung

Der Burnikel-Ziegler-Algorithmus kommt in Java ab Version 8 , GMP und der Algorithmenbibliothek Leda zum Einsatz.