Алгоритм Бурникеля — Циглера
Алгоритм Бурникеля — Циглера (нем. Burnikel-Ziegler-Verfahren) — быстрый алгоритм деления больших целых чисел, описанный Кристофом Бурникелем и Йоахимом Циглером в 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> в числе прочего производит умножение, поэтому его быстродействие можно увеличить использованием методов быстрого умножения (см. ниже).
Вычислительная сложность
Вычислительная сложность алгоритма зависит от используемого при расчётах метода умножения. Если при расчётах используется алгоритм, вычислительная сложность которого составляет <math>O(n^c)</math>, например, алгоритм Карацубы или Тоома — Кука[en], то сложность алгоритма Бурникеля — Циглера будет также составлять <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]:11
На практике алгоритм Бурникеля — Циглера быстродейственнее деления столбиком и алгоритма Барретта[en] для чисел, количество десятичных разрядов в которых лежит между приблизительно 250 и 1,5 млн.[1]:22
Применение
Алгоритм Бурникеля — Циглера используется в библиотеках Java версии 8[2] и GMP.[3]
Напишите отзыв о статье "Алгоритм Бурникеля — Циглера"
Примечания
- ↑ 1 2 3 4 Christoph Burnikel; Joachim Ziegler. [cr.yp.to/bib/1998/burnikel.ps Fast Recursive Division] (англ.). Max-Planck-Institut für Informatik (October 1998). Проверено 27 июня 2014.
- ↑ [bugs.sun.com/bugdatabase/view_bug.do?bug_id=8014319 JDK-8014319 : Faster division of large integers] (англ.). Oracle. Проверено 27 июня 2014.
- ↑ [gmplib.org/manual/Divide-and-Conquer-Division.html Divide and Conquer Division] (англ.). gmplib.org. Проверено 27 июня 2014.
Отрывок, характеризующий Алгоритм Бурникеля — Циглера
«Как он думает это легко, – подумал Пьер. – Он не знает, как это страшно, как опасно. Слишком рано или слишком поздно… Страшно!»– Как же изволите приказать? Завтра изволите ехать? – спросил Савельич.
– Нет; я немножко отложу. Я тогда скажу. Ты меня извини за хлопоты, – сказал Пьер и, глядя на улыбку Савельича, подумал: «Как странно, однако, что он не знает, что теперь нет никакого Петербурга и что прежде всего надо, чтоб решилось то. Впрочем, он, верно, знает, но только притворяется. Поговорить с ним? Как он думает? – подумал Пьер. – Нет, после когда нибудь».
За завтраком Пьер сообщил княжне, что он был вчера у княжны Марьи и застал там, – можете себе представить кого? – Натали Ростову.
Княжна сделала вид, что она в этом известии не видит ничего более необыкновенного, как в том, что Пьер видел Анну Семеновну.
– Вы ее знаете? – спросил Пьер.
– Я видела княжну, – отвечала она. – Я слышала, что ее сватали за молодого Ростова. Это было бы очень хорошо для Ростовых; говорят, они совсем разорились.
– Нет, Ростову вы знаете?
– Слышала тогда только про эту историю. Очень жалко.
«Нет, она не понимает или притворяется, – подумал Пьер. – Лучше тоже не говорить ей».
Княжна также приготавливала провизию на дорогу Пьеру.
«Как они добры все, – думал Пьер, – что они теперь, когда уж наверное им это не может быть более интересно, занимаются всем этим. И все для меня; вот что удивительно».
В этот же день к Пьеру приехал полицеймейстер с предложением прислать доверенного в Грановитую палату для приема вещей, раздаваемых нынче владельцам.
«Вот и этот тоже, – думал Пьер, глядя в лицо полицеймейстера, – какой славный, красивый офицер и как добр! Теперь занимается такими пустяками. А еще говорят, что он не честен и пользуется. Какой вздор! А впрочем, отчего же ему и не пользоваться? Он так и воспитан. И все так делают. А такое приятное, доброе лицо, и улыбается, глядя на меня».
Пьер поехал обедать к княжне Марье.
Проезжая по улицам между пожарищами домов, он удивлялся красоте этих развалин. Печные трубы домов, отвалившиеся стены, живописно напоминая Рейн и Колизей, тянулись, скрывая друг друга, по обгорелым кварталам. Встречавшиеся извозчики и ездоки, плотники, рубившие срубы, торговки и лавочники, все с веселыми, сияющими лицами, взглядывали на Пьера и говорили как будто: «А, вот он! Посмотрим, что выйдет из этого».
