biginteger - Division of Large numbers

Question

Is there any faster method for division of large integers(having 1000 digits or more) other than the school method?

Answer 1

Wikipedia lists multiple division algorithms. See Computational complexity of mathematical operations which lists Schoolbook long division as O(n^2) and Newton's method as M(n) where M is the complexity of the multiplication algorithm used, which could be as good as O(n log n 2^(log*n)) asymptotically.

Note from the discussion of one of the multiplication algorithms that the best algorithm asymptotically is not necessarily the fastest for "small" inputs:

In practice the Sch?nhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2^(2^15) to 2^(2^17) (10,000 to 40,000 decimal digits). The GNU Multi-Precision Library uses it for values of at least 1728 to 7808 64-bit words (111,000 to 500,000 decimal digits), depending on architecture. There is a Java implementation of Sch?nhage–Strassen which uses it above 74,000 decimal digits.