Есть ли более быстрый метод для деления больших целых чисел (имеющий 1000 цифр или более), кроме школьного метода?
Википедия списки несколько алгоритмов деления . См. Вычислительная сложность математических операций , в которой перечислено Длинное деление учебника как O(n^2) и Метод Ньютона как M(n), где M - сложность умножения используемый алгоритм, который может быть асимптотически равен O(n log n 2^(log*n)).
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 десятичных цифр.