[Phys-L] Re: Division via subtractions

[Stefan Jeglinski <jeglin@4PI.COM>]

> Stefan Jeglinski wrote:
>
>  > Indeed, the two modern Digital Signal Processors I have worked
>  > with both do division by subtraction. I doubt either TI or
>  > Analog Devices would consider it laughable.
> ....
>  > Of course, division is extremely expensive on a DSP because of
>  > this method. Typically, a 16-bit division takes 16 clock
>  > cycles, whereas multiplication takes one clock cycle,
>
> Bingo!  That timing info strongly suggests that TI and Analog
> Devices are using long division.  It proves they cannot be
> using division-by-subtraction.  The latter consists of simply
> subtracting the same thing over and over again while counting,
> and would require roughly 2^16 clock cycles if there are 16
> bits in the quotient.

There must be a semantic problem I'm not getting. I will go back and
reread what John wrote in previous posts. In the meantime, interested
readers may chew on this fairly concise example:

http://www.clipx.net/ng/tmslink/ng52afb.php

In which the process is described as both [similar to] long division
-and- repeated subtraction. Regardless, the process involves one
"subtraction operation" per bit, so even though it is much more
expensive than multiplication, it is not a 2^N process.

I'm not getting why John's definition of "division-by-subtraction" is
a 2^N process.


> There's an exponentially huge difference between
>    sub-shift-sub-shift-sub (aka long division) and
>    sub-sub-sub-sub-sub-sub-sub-sub (aka subtraction
> by division).

OK, I'm beginning to see the point, as the sub-shift operation is
explicit in the linked example, but my eyes can't take it any more
tonight.


Stefan Jeglinski