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 Schritte benötigt, wie es beim Karazuba- und dem Toom-Cook-Algorithmus der Fall ist, läuft die Burnikel-Ziegler-Division ebenfalls in Schritten abhttps://cr.yp.to/bib/1998/burnikel.ps S. 11: Die Division zweier Zahlen der Länge und benötigt , wobei die Multiplikationskomplexität ist, also z. B. im Fall der Karazuba-Multiplikation.. Liegt die Multiplikationskomplexität bei , was dem Schönhage-Strassen-Algorithmus entspricht, so verringert sich die Komplexität der Division auf https://cr.yp.to/bib/1998/burnikel.ps Abschnitt 4.3.
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 und , die Zahlen der Länge und bzw. und 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 führt darüber hinaus eine Multiplikation durch und profitiert von schnellen Multiplikationsalgorithmen (s. o.).
Dritter Bestandteil ist ein Algorithmus namens , der die Ausgangszahlen so aufteilt, dass sie für geeignet sind.
Verwendung Der Burnikel-Ziegler-Algorithmus kommt in Java ab Version 8 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=8014319, GMPhttps://gmplib.org/manual/Divide-and-Conquer-Division.html und der Algorithmenbibliothek Leda zum Einsatz.
Einzelnachweise
Kategorie:Zahlentheoretischer Algorithmus Kategorie:Computerarithmetik Kategorie:Division (Mathematik)