# Fast algorithm for modular division (residue)

I'm looking for a fast algorithm to perform division of large numbers (by hand). Traditional long division just isn't fast enough for my needs.

In most of these cases, I'm only looking for the modulus/remainder of the division, so if there is a fast algorithm specifically for this purpose, it would suffice. (But, if there is a way to get the quotient as well, it would also help).

Edit: Now that I think about it, the algorithm for synthetic division/synthetic substitution involves no division (and addition/multiplication is typically easier and faster than division). Is there perhaps a clever way to adapt this algorithm for fast numerical division?

-
When you say "by hand," how large are the numbers involved here, and what exactly are your needs? –  Qiaochu Yuan Oct 10 '10 at 0:02

## 1 Answer

The key idea is to make a good estimate of the quotient based on the most significant digits of the dividend and divisor. This is described in detail in the division algorithm presented in section 4.3.1 of Knuth, The art of computer programming, Volume 2, Seminumerical algorithms - the standard reference. Similar ideas (Lehmer at al.) are used in optimizing the computation of the remainder sequence in the Euclidean algorithm for the GCD, which is also described in Knuth's book, viz. p. 345, section 4.5.2.

-