From: Scott Dattalo <scott@da...>  20020320 14:19:49

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 