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

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

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

Если при расчётах используется алгоритм, вычислительная сложность которого составляет , например, алгоритм Карацубы или Тоома — Кука, то сложность алгоритма Бурникеля — Циглера будет также составлять . Если в вычислениях используется метод умножения Шёнхаге — Штрассена с , то сложность деления составит [1]:11

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

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

Примечания

  1. Christoph Burnikel; Joachim Ziegler. Fast Recursive Division (англ.). Max-Planck-Institut für Informatik (октябрь 1998). Дата обращения: 27 июня 2014.
  2. JDK-8014319 : Faster division of large integers (англ.). Oracle. Дата обращения: 27 июня 2014.
  3. Divide and Conquer Division (англ.). gmplib.org. Дата обращения: 27 июня 2014.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.