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

Question

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

Answer 1

Списки Википедии multiple division algorithms. См Computational complexity of mathematical operations которой перечислены Schoolbook long division в O(n^2) и Newton's method, как M(n) где M является сложность алгоритма умножения используется, что может быть столь же хорошо, как O(n log n 2^(log*n)) асимптотически.

Примечание от обсуждения one of the multiplication algorithms, что лучший алгоритм асимптотически не обязательно являются самыми быстрыми для «маленьких» входы:

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