Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.