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

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

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

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

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

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