Русская Википедия:Алгоритм Бурникеля — Циглера

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

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

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

Примечания

Шаблон:Примечания

Шаблон:Теоретико-числовые алгоритмы