Re: division algorithm

From: Thad Smith (ThadSmith_at_acm.org)
Date: 03/21/04 

Date: Sat, 20 Mar 2004 23:15:44 -0700

Gerry Quinn wrote:
>
> In article <c3end3$4mg$1@inews.gazeta.pl>, "ArturS" <mail_skrzynka@CUTTHISwp.pl> wrote:
> >hi,
> >Does anyone know how to divide one 2-bytes number by another which is 1-byte
> >long ; there are only one-byte registers available (microcontroller 8051).
> >Any suggestions ?
>
> A simple way might be to get a lower limit by dividing separately into
> the upper and lower bytes - then correct by subtraction.

Not really. When you work out the details, you still do a lot of
shifting and comparing. You're better off with the standard shift and
subtract.

In general if you require an integer division which exceeds the capacity
of the native divide instruction, you have a decision to either

1) implement a shift and subtract loop, with one bit generated each
pass, or
2) use the divide instruction to generate a trial divisor, which you can
then multiply by the divisor and subtract from the working remainder of
the numerator.

For the second method, you usually generate one full word (divisor
width) of quotient on a single pass, subject to correction if the trial
divisor was wrong. There is a setup operation, though, to normalize the
numerator and divisor to get the highest number of bits per iteration.

I suspect that the optimum switching point between shift/subtract loop
and word-wide trial divisor is around 20 - 100 bits of quotient, as far
as speed optimization goes. The trial divisor method requires a lot
more code and attention to details, though.

The Borland Turbo C library which supported the 16-bit 808x family used
a shift and subtract loop for 32/32 integer divides, even though a 32/16
bit divide was native.

Thad

Relevant Pages

  • Re: How to perform integer div with SIMD?
    ... First, use the approximate reciprocal lookup to generate a set of starting values, then one or two NR iterations (also in SIMD fp mode) to get a more precise value. ... If negative, subtract one from the result, add divisor to remainder. ...
    (comp.lang.asm.x86)
  • Re: Nth Prime
    ... > square-root that divides that number, will yield a number smaller than the ... compare the trial divisor to the quotient produced by the division. ... When the quotient is less than the divisor, ...
    (alt.lang.asm)