Das Burnikel-Ziegler-Verfahren ist ein 1998 von Christoph Burnikel und Joachim Ziegler[1] 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 ab[2]. Liegt die Multiplikationskomplexität bei , was dem Schönhage-Strassen-Algorithmus entspricht, so verringert sich die Komplexität der Division auf [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.[4][5]

Beschreibung

Bearbeiten

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

Bearbeiten

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

Einzelnachweise

Bearbeiten
  1. Forschungsbericht MPI-I-98-1-022. Abgerufen am 8. Januar 2012 (englisch).
  2. http://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.
  3. http://cr.yp.to/bib/1998/burnikel.ps Abschnitt 4.3
  4. Forschungsbericht MPI-I-98-1-022. Abgerufen am 8. Januar 2012 (englisch): „From Figure 5 we see that the break-even point is about 26 digits, i. e., FastDivision [Anm.: Gemeint ist der Burnikel-Ziegler-Alg.] pays for numbers with more than 250 decimal digits or 832 bits.“
  5. Fast Division of large Integers. (PDF; 565 kB) Archiviert vom Original am 25. November 2011; abgerufen am 22. März 2023 (englisch): „The competition mainly consists of a recursive algorithm by Burnikel and Ziegler. […] The breakeven point seems to be at around   bits, or 1.5 million decimal digits.“
  6. http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=8014319
  7. http://gmplib.org/manual/Divide-and-Conquer-Division.html