Алгоритм Бурникеля — Циглера () — алгоритм деления больших целых чисел, описанный Кристофом Бурникелем и Йоахимом Циглером в 1998 году, позволяющий эффективно вычислить и частное, и остаток от деления.
Ядром метода являются алгоритмы и , которые делят числа длинами , , , . Алгоритмы вызывают друг друга рекурсивно, с каждым шагом сокращая длину числителя на 1/4 и 1/3 соответственно. Алгоритм в числе прочего производит умножение, поэтому его быстродействие можно увеличить использованием .
Если при расчётах используется алгоритм, вычислительная сложность которого составляет , например, алгоритм Карацубы или Тоома — Кука, то сложность алгоритма Бурникеля — Циглера будет также составлять . Если в вычислениях используется метод умножения Шёнхаге — Штрассена с , то сложность деления составит
На практике алгоритм быстрее деления столбиком и алгоритма Барретта для чисел, количество десятичных разрядов в которых лежит между приблизительно 250 и 1,5 млн.
Используются во многих стандартных программных библиотеках, например, в Java версии 8 и GMP.
Примечания
Категория:Появились в 1998 году Категория:Деление Категория:Длинная арифметика