>> I've been writing a series of articles on multi-word arithmetic for
>> Embedded Systems Programming magazine. I've gotten to the point of
>> integer division, and am looking for an algorithm that does fast
>> multi-word division. I've heard there's an iterative algorithm that's
>> used in some CPU's, but the only one I've been able to devise is not
>> fast enough.
>> Can anyone point me in the right direction for such an algorithm?
>You might have Newton's method in mind. I used it decades ago on
>machines that didn't have divide instructions. See, for example, Knuth
>(The Art of Computer Programming, vol. 2, section 4.3.1) where some of
>the ideas in 'History and Bibliography' might be what you want. A
>similar approach is in Press, et al (Numerical Recipes in ..., section
>20.6). Note carefully that Newton's method for division requires a
>reasonably accurate initial estimate (within a factor of 2) for
Yes. You'll find an elegant example in Struble: Assembly-language
Programming for the IBM S/370, using the double-precision divider
to produce the initial approximation, and the quadruple precision
multiplier to produce the next iterate in quadruple precision.
OTOMH, it requires just a few steps.