Loading AI tools
алгоритм деления больших целых чисел Из Википедии, свободной энциклопедии
Алгоритм Бурникеля — Циглера (нем. Burnikel-Ziegler-Verfahren) — алгоритм деления больших целых чисел, описанный Кристофом Бурникелем и Йоахимом Циглером в 1998 году[1], позволяющий эффективно вычислить и частное, и остаток от деления.
Ядром метода являются алгоритмы и , которые делят числа длинами , , , . Алгоритмы вызывают друг друга рекурсивно, с каждым шагом сокращая длину числителя на 1/4 и 1/3 соответственно[1]. Алгоритм в числе прочего производит умножение, поэтому его быстродействие можно увеличить использованием методов быстрого умножения[англ.].
Если при расчётах используется алгоритм, вычислительная сложность которого составляет , например, алгоритм Карацубы или Тоома — Кука, то сложность алгоритма Бурникеля — Циглера будет также составлять . Если в вычислениях используется метод умножения Шёнхаге — Штрассена с , то сложность деления составит [1]:11
На практике алгоритм быстрее деления столбиком и алгоритма Барретта для чисел, количество десятичных разрядов в которых лежит между приблизительно 250 и 1,5 млн[1]:22.
Используются во многих стандартных программных библиотеках, например, в Java версии 8[2] и GMP[3].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.