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

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

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

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

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

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