On Wed, 20 Mar 2002, Bernhard Held wrote:
> > Does anybody know where to find source of a very fast division of 18bit /
> > 15bit ?
> What processor? For the 8051you'll find assembler functions for 16/16 and
> 32/32 bit divisions in the library. It should be easy to adjust the source
> for 18/15 bit. Additionally you can eliminate the loop. AFAIK there is no
> faster algorithm for the 8051, if there's no further infomation about the
> distribution of the values.
Yeah, which processor?
There are always tricks one can play. A generic solution to this problem
would be to unroll the division loop. This saves decrementing a loop
counter and a branch.
If you know something about the form of the numbers, there are additional
tricks. For example, if your divisor is actually a constant, then it's
often faster to multiply by it's reciprocal. Or if you know that the
upper bits are constant, then you can try this formula:
x/y = x / (y_up + y_lo)
= x / y_up * (1/(1 + y_lo/y_up))
A series expansion of
1
 = 1  A + A^2  A^3
1 + A
May be then invoked. This is especially useful for the case when y_up is
way greater than y_lo because then only a few terms of the expansion are
needed. Intelligent partitioning can turn some of the division operations
into shift operations.
There are many, many tricks. But each trick depends on the specific
problem to be solved.
Scott
