Multi-word division?
Author Message
Multi-word division?

>>
>> 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?
>>
>> Thanks,
>>
>> Jack

>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
>convergence.

>Lynn Killingbeck

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.

Fri, 03 Dec 1999 03:00:00 GMT
Multi-word division?

Quote:

> 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.

Thanks for the info, Robin.

Jack

Sun, 05 Dec 1999 03:00:00 GMT

 Page 1 of 1 [ 2 post ]

Relevant Pages