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

Ядром метода являются алгоритмы ${\displaystyle D_{2n/1n}}$ и ${\displaystyle D_{3n/2n}}$ , которые делят числа длинами ${\displaystyle 2n}$ , ${\displaystyle 1n}$ , ${\displaystyle 3n}$ , ${\displaystyle 2n}$ . Алгоритмы вызывают друг друга рекурсивно, с каждым шагом сокращая длину числителя на 1/4 и 1/3 соответственно . Алгоритм ${\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)}$ ^:11

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

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

Примечания