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

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

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

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

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

Ответ 1

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

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

Ответ 2

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

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

Ответ 3

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

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