[Phys-L] Re: Division via subtractions

[John Denker <jsd@AV8N.COM>]

Michael Edmiston wrote:

> As an assembly-language programmer I had a pretty big bag of tricks.

I assume it was big enough to contain implementations of
  -- long division
  -- tables of logarithms and antilogarithms
  -- etc.

> Division by subtraction was in the bag.  Sometimes it was appropriate
> and sometimes it was not.

Please explain.  When is it appropriate to use an algorithm
that requires roughly 2^N subtractions in place of one that
requires only N subtractions?  (Here N is the number of bits
in the quotient.)

The logarithm approach is even faster still, but comes at
some cost of space.  You'd have to be pretty desperate to
argue against long division for space reasons, since the
usual implementations are quite svelte.  For anyone who
doesn't know exactly what the code looks like, see Knuth
volume I, or perhaps
http://www.everything2.com/index.pl?node_id=1023414&lastnode_id=11461

Open-ended question: Suppose division-by-subtraction had been
missing from the bag of tricks.  Would anyone have regretted
using long division?  How much regret?  Why?

==============
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'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).

====================

Karl Trappe wrote:
> Wow, John.  You must be teaching to a different 4th grade
> audience (the grade where division is typically taught), than
> any which I have encountered.
>
> If I encountered such a statement, I would, minimally, be
> curious where the student learned the concept, and what
> "multiplicative inverse" meant to him/her in *other* words
> which are part of a 4th grader's vocabulary.  Worse, yet, I
> would see if the student could convey this concept to anybody
> who was "just learning" to perform division, ie, let the
> student be a peer tutor.  And then, I'd get the student to
> teach relativity and quantum mechanics for the next 4th grade
> trick (smile).

I get 663 hits from
   http://www.google.com/search?q=inverse+identity+4th-grade

That can be contrasted with 3890 hits from
   http://www.google.com/search?q=long-division+4th-grade

which puts me in the minority, but doesn't put me in the loony
bin.