Алгоритм Бурникеля — Циглера

Алгоритм Бурникеля — Циглера (нем. Burnikel-Ziegler-Verfahren) — алгоритм деления больших целых чисел, описанный Кристофом Бурникелем и Йоахимом Циглером в 1998 году[1], позволяющий эффективно вычислить и частное, и остаток от деления.

Ядром метода являются алгоритмы ${\displaystyle D_{2n/1n}}$ и ${\displaystyle D_{3n/2n}}$, которые делят числа длинами ${\displaystyle 2n}$, ${\displaystyle 1n}$, ${\displaystyle 3n}$, ${\displaystyle 2n}$. Алгоритмы вызывают друг друга рекурсивно, с каждым шагом сокращая длину числителя на 1/4 и 1/3 соответственно[1]. Алгоритм ${\displaystyle D_{3n/2n}}$ в числе прочего производит умножение, поэтому его быстродействие можно увеличить использованием методов быстрого умножения^[англ.].

Если при расчётах используется алгоритм, вычислительная сложность которого составляет ${\displaystyle O(n^{c})}$, например, алгоритм Карацубы или Тоома — Кука, то сложность алгоритма Бурникеля — Циглера будет также составлять ${\displaystyle O(n^{c})}$. Если в вычислениях используется метод умножения Шёнхаге — Штрассена с ${\displaystyle O(n\log n\log \log n)}$, то сложность деления составит ${\displaystyle O(n\log ^{2}n\log \log n)}$[1]:11

На практике алгоритм быстрее деления столбиком и алгоритма Барретта для чисел, количество десятичных разрядов в которых лежит между приблизительно 250 и 1,5 млн[1]:22.

Используются во многих стандартных программных библиотеках, например, в Java версии 8[2] и GMP[3].

Примечания

1. Christoph Burnikel; Joachim Ziegler.: Fast Recursive Division (англ.). Max-Planck-Institut für Informatik (октябрь 1998). Дата обращения: 27 июня 2014. Архивировано 3 декабря 2013 года.
2. JDK-8014319 : Faster division of large integers (англ.). Oracle. Дата обращения: 27 июня 2014. Архивировано 3 декабря 2013 года.
3. Divide and Conquer Division (англ.). gmplib.org. Дата обращения: 27 июня 2014. Архивировано 5 декабря 2013 года.