WikiSort.ru - Не сортированное

Алгоритм Бурникеля — Циглера (нем. 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})}$ , например, алгоритм Карацубы или Тоома — Кука^[en], то сложность алгоритма Бурникеля — Циглера будет также составлять ${\displaystyle O(n^{c})}$ . Если в вычислениях используется метод умножения Шёнхаге — Штрассена с ${\displaystyle O(n\log n\log \log n)}$ , то сложность деления составит ${\displaystyle O(n\log ^{2}n\log \log n)}$ ^[1]:11

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

Применение

Алгоритм Бурникеля — Циглера используется в библиотеках Java версии 8^[2] и GMP^[3].

Примечания