Отдел больших чисел

Есть ли более быстрый метод деления больших целых чисел (имеющих 1000 и более цифр), кроме школьного метода?


division biginteger
person Jonh    schedule 13.02.2012    source источник
comment
Я предполагаю, что @prashanthkvs означает деление в длину.   -  person perelman    schedule 13.02.2012
comment
Основной метод деления, который мы используем для целых чисел, который мы можем моделировать для больших целых чисел. Я спрашиваю об этом, так как видел другие методы, такие как поиск обратного, но я не уверен, что они всегда будут давать правильные результаты.   -  person Jonh    schedule 13.02.2012

Ответы (1)


arrow_upward
6
arrow_downward

В Википедии перечислены множественные алгоритмы деления. См. раздел Вычислительная сложность математических операций, в котором перечислены Длинное деление школьного учебника как O(n^2) и метод Ньютона как M(n), где M — сложность используемого алгоритма умножения, который может быть равен O(n log n 2^(log*n)) асимптотически.

Обратите внимание на обсуждение одного из алгоритмов умножения, что асимптотически лучший алгоритм не обязательно является самым быстрым для «маленьких» входных данных:

На практике алгоритм Шёнхаге-Штрассена начинает превосходить старые методы, такие как умножение Карацубы и Тума-Кука, для чисел от 2 ^ (2 ^ 15) до 2 ^ (2 ^ 17) (от 10 000 до 40 000 десятичных цифр). Библиотека GNU Multi-Precision использует ее для значений от 1728 до 7808 64-битных слов (от 111 000 до 500 000 десятичных цифр), в зависимости от архитектуры. Существует Java-реализация Шёнхаге-Штрассена, в которой используется более 74 000 десятичных цифр.

person perelman    schedule 13.02.2012