Как реализовать (быстрое) разделение Bigint?

Question

В настоящее время я делаю свой собственный класс BigInt, разделив числа на 7 цифр.(т.е. в базе 10 000 000)

Я реализовал сложение, вычитание и умножение, а теперь я реализую деление и мод.Я написал код, который выполняет деление на длинное деление (вычисление чисел путем деления старших значащих цифр), и оно работает.

Однако это слишком медленно.Когда я проверяю операции над 108-значным числом и 67-значным числом, для вычисления деления требуется 1,9 мс, что намного медленнее, чем другие операции (0,007 ~ 0,008 мс для вычисления сложения / вычитания, 0,1 мс для вычисления умножения).

Как и алгоритм Карацубы и БПФ для быстрого умножения, какой алгоритм существует для вычисления деления? Википедия демонстрирует некоторые алгоритмы деления (которые вычисляют мультипликативное обратное делителя и умножают его на дивиденд), но я думаю, что это не очень помогает в реализации деления.Я тоже читаю разделы "Методы большого целого", но это мне тоже не помогает ...: (

Answer 1

Стандартным справочником по арифметике с большими целыми числами является книга Дональда Кнута Искусство компьютерного программирования , том 2, раздел 4.3.Его алгоритм деления - в основном алгоритм начальной школы, с некоторыми небольшими улучшениями.

Кстати, большинство людей , которые реализуют арифметику с большими целыми числами, используют степень два, а не степеньдесять как основа их системы счисления.

Answer 2

Для достаточно быстрого алгоритма деления, посмотрите на http://myweb.lmu.edu/dmsmith/MComp1996.pdf

Это все еще O (n ^ 2), но эффективно для умеренных длин. Это особенно хорошо подходит, когда вы используете базы, которые меньше, чем размер слова. Несколько лет назад я реализовал это на Python. Код похоронен в http://home.comcast.net/~casevh/decint_041.tar.gz. Найдите функции smithdiv () и remainder_norm ().

Answer 3

Я бы посоветовал вам взглянуть на исходный код библиотеки GMP и перенести необходимые вам функции на JavaScript, или получить представление о том, как это делается.

Еслиесть хороший алгоритм, скорее всего, у этой библиотеки он есть;и распространяется под LGPL.