Burnikel-Ziegler-Verfahren

Das Burnikel-Ziegler-Verfahren ist ein 1998 von Christoph Burnikel und Joachim Ziegler<ref>Vorlage:Cite book/Name: [ Forschungsbericht MPI-I-98-1-022.] , archiviert vom Vorlage:IconExternal (nicht mehr online verfügbar) am Vorlage:Cite book/URL; abgerufen am 8. Januar 2012 (). Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/Meldung2Vorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung</ref> 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 <math>O(n^c)</math> Schritte benötigt, wie es beim Karazuba- und dem Toom-Cook-Algorithmus der Fall ist, läuft die Burnikel-Ziegler-Division ebenfalls in <math>O(n^c)</math> Schritten ab<ref>https://cr.yp.to/bib/1998/burnikel.ps S. 11: Die Division zweier Zahlen der Länge <math>r</math> und <math>s</math> benötigt <math>O\left(\frac{r}{s} \cdot (K(s)+O(s\log s)\right)</math>, wobei <math>K(s)</math> die Multiplikationskomplexität ist, also z. B. <math>O(s^{\log 3})</math> im Fall der Karazuba-Multiplikation.</ref>. Liegt die Multiplikationskomplexität bei <math>O(n \cdot \log(n) \cdot \log (\log n))</math>, was dem Schönhage-Strassen-Algorithmus entspricht, so verringert sich die Komplexität der Division auf <math>O(n \cdot \log^2(n) \cdot \log(\log n))</math><ref>https://cr.yp.to/bib/1998/burnikel.ps Abschnitt 4.3</ref>.

In der Praxis ist der Burnikel-Ziegler-Algorithmus zwischen ca. 250 und 1,5 Millionen Dezimalstellen schneller als die Schulmethode und das Barrett-Verfahren.<ref>Vorlage:Cite book/Name: [ Forschungsbericht MPI-I-98-1-022.] , archiviert vom Vorlage:IconExternal (nicht mehr online verfügbar) am Vorlage:Cite book/URL; abgerufen am 8. Januar 2012 (): „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.“ Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/Meldung2Vorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung</ref><ref>Vorlage:Cite book/Name: [ Fast Division of large Integers.] (PDF; 565 kB) , archiviert vom Vorlage:IconExternal (nicht mehr online verfügbar) am Vorlage:Cite book/URL; abgerufen am 22. März 2023 (): „The competition mainly consists of a recursive algorithm by Burnikel and Ziegler. […] The breakeven point seems to be at around <math>5 \cdot10^6</math> bits, or 1.5 million decimal digits.“ Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/Meldung2Vorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung</ref>

Beschreibung

Kernstück des Algorithmus sind zwei Unteralgorithmen namens <math>D_{2n/1n}</math> und <math>D_{3n/2n}</math>, die Zahlen der Länge <math>2n</math> und <math>1n</math> bzw. <math>3n</math> und <math>2n</math> 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 <math>D_{3n/2n}</math> führt darüber hinaus eine Multiplikation durch und profitiert von schnellen Multiplikationsalgorithmen (s. o.).

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

Verwendung

Der Burnikel-Ziegler-Algorithmus kommt in Java ab Version 8 <ref>http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=8014319</ref>, GMP<ref>https://gmplib.org/manual/Divide-and-Conquer-Division.html</ref> und der Algorithmenbibliothek Leda zum Einsatz.

Einzelnachweise

<references />