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

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

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

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

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

источник

2012-01-16 JiminP

Хороший вопрос, но вы можете рассмотреть http://programmers.stackexchange.com вместо stackoverflow. –

Простой поиск в Google демонстрирует тоны статьи об этом, я не думаю, что это простая работа, но основная идея - это быстрое умножение, и все алгоритмы вокруг этого. например, вы можете взглянуть на [быстрое деление на большие целые числа] (http://www.treskal.com/kalle/exjobb/original-report.pdf) –

Есть ли шанс, что вы можете открыть источник? В настоящее время в JS нет хорошей библиотеки bigint. –

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

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

источник

2012-01-16 17:34:19 copy

Вы также можете использовать компилятор LLVM -> javascript (emscripten) для автоматического переноса всей библиотеки. – Raynos

@Raynos. Я бы не поставил на вывод emscripten, который может быть вызван из JS без серьезной боли, и особенно не по версиям emscription. – delnan

Я прочитал несколько кодов ('divexact.c' и' divegcd.c'), и кажется, что включены побитовые операции, которые я не могу реализовать (потому что я представляю числа в базе 10^7) ... – JiminP

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

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

источник

2012-01-16 20:37:11 user448810

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

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

источник

2012-01-17 16:46:42 casevh

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

ответ

Смежные вопросы