Burnikel-Ziegler method

The Burnikel-Ziegler process is a 1998 by Christoph Burnikel and Joachim Ziegler described Divisions - algorithm for integers. In addition to the quotient, it also calculates the rest .

The runtime complexity depends on the multiplication algorithm used. If the multiplication requires steps, as is the case with the Karazuba and Toom-Cook algorithms , the Burnikel-Ziegler division also takes place in steps. If the multiplication complexity is included , which corresponds to the Schönhage-Strassen algorithm , the complexity of the division is reduced to . ${\ displaystyle O (n ^ {c})}$ ${\ displaystyle O (n ^ {c})}$ ${\ displaystyle O (n \ cdot \ log (n) \ cdot \ log (\ log n))}$ ${\ displaystyle O (n \ cdot \ log ^ {2} (n) \ cdot \ log (\ log n))}$

In practice, the Burnikel-Ziegler algorithm is between approx. 250 and 1.5 million decimal places faster than the Schul method and the Barrett method .

description

The core of the algorithm are two sub-algorithms called and , which divide the numbers of length and or and and call each other recursively . With each call, the length of the number is reduced by 1/4 or 1/3; additions, subtractions, shifts and elementary divisions are used. The sub-algorithm also carries out a multiplication and benefits from fast multiplication algorithms (see above). ${\ displaystyle D_ {2n / 1n}}$ ${\ displaystyle D_ {3n / 2n}}$ ${\ displaystyle 2n}$ ${\ displaystyle 1n}$ ${\ displaystyle 3n}$ ${\ displaystyle 2n}$ ${\ displaystyle D_ {3n / 2n}}$

The third component is an algorithm called that divides the seed numbers so that they are suitable for. ${\ displaystyle D_ {r / s}}$ ${\ displaystyle D_ {2n / 1n}}$

use

The Burnikel-Ziegler algorithm is used in Java version 8 and higher , GMP and the Leda algorithm library .

Individual evidence

↑ Research Report MPI-I-98-1-022 (English) . Retrieved January 8, 2012.

↑ http://cr.yp.to/bib/1998/burnikel.ps p. 11: The division of two numbers of length and required , where the multiplication complexity is, so z. B. in the case of the Karazuba multiplication.

{\ displaystyle r}

{\ displaystyle s}

{\ displaystyle O \ left ({\ frac {r} {s}} \ cdot (K (s) + O (s \ log s) \ right)}

{\ displaystyle K (s)}

{\ displaystyle O (s ^ {\ log 3})}

↑ http://cr.yp.to/bib/1998/burnikel.ps Section 4.3

↑ Research Report MPI-I-98-1-022 (English) . Retrieved January 8, 2012: “From Figure 5 we see that the break-even point is about 26 digits, i. e., FastDivision [Note: This refers to the Burnikel-Ziegler Alg.] pays for numbers with more than 250 decimal digits or 832 bits. "

↑ Fast Division of large integers ( PDF; 579 kB) Archived from the original on November 25, 2011. Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. Retrieved January 8, 2012: “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. " @1@ 2 ${\ displaystyle 5 \ cdot 10 ^ {6}}$

↑ http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=8014319

↑ http://gmplib.org/manual/Divide-and-Conquer-Division.html

[1] Research Report MPI-I-98-1-022 (English) . Retrieved January 8, 2012.

[2] ttp://cr.yp.to/bib/1998/burnikel.ps p. 11: The division of two numbers of length and required , where the multiplication complexity is, so z. B. in the case of the Karazuba multiplication. ${\ displaystyle r}$ ${\ displaystyle s}$ ${\ displaystyle O \ left ({\ frac {r} {s}} \ cdot (K (s) + O (s \ log s) \ right)}$ ${\ displaystyle K (s)}$ ${\ displaystyle O (s ^ {\ log 3})}$

[3] ttp://cr.yp.to/bib/1998/burnikel.ps Section 4.3

[4] Research Report MPI-I-98-1-022 (English) . Retrieved January 8, 2012: “From Figure 5 we see that the break-even point is about 26 digits, i. e., FastDivision [Note: This refers to the Burnikel-Ziegler Alg.] pays for numbers with more than 250 decimal digits or 832 bits. "