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

Алгоритм Бурникеля — Циглера (нем. 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].