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

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

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

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

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

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