Scott Dattalo wrote:
>
> Vladimir M. Klochko wrote:
>


  In all of these responses, I haven't seen anyone mention proper long
division as being the correct response to "what's the inverse of
multiply x by x?"

  First, note that the normal multiply routines everyone uses are really
the standard "long multiply".  The shortcuts of shifting and etc come
from the binary system's 0 or 1 multiplier, NOT from some special way
of multiplying.  You can use the same tricks to multiply 543965 by 10110
decimal with shifts and adds.  It's still long multiplication, just
optimized for the number system.

  Second, a lot of people seem to think "integer" math can't do
fractions.  Not so at all, and it's easy..
                1/1/1/
        4 2 1 . 2 4 8

        x x x . x x x

Take multiplication:   (kinda hard to format this crap!)

     111   Is it :   7    or 3 1/2     11.1   or 1 3/4     1.11
x    111             7       3 1/2     11.1      1 3/4     1.11
--------            --       -----     ----      -----     ----
  110001            49       12.25   1100.01     3.0625   11.0001

They are all the same, just a matter of where you put the decimal
(actually, binary) point and keeping track of it.

  Just like in decimal :
   325   or   3.25
X  456        4.56
------       -----
148200       14.82

  You can do the rest..

  Now, say you wanted to divide 21 by 6 in decimal:

  #1 You wouldn't think of doing something as corny as converting to
     floating point to do it!  (So why does everyone think that is the
     best way to do it for binary fractions on a microcontroller?)

  #2 You'd do it like this:           Same as:

              3.5                            011.1
           ______                         __________
       6  |  21.0                    110 | 10101.0
            -18                             110
              3.0                           ----
              3.0                           1001
                0                            110
                                            ------
                                              11.0
                                              11.0
                                              ----
                                                 0

  #3 One more 25/5:  (draw your own lines!)


                 101.
        101    11001.00000000000
               101
                0101            5 times 2 is too large so drop next
                 101              digit just like decimal.
                   0

  Works just like decimal AND there are some shortcuts just like
multiply.  In multiply, you get to skip the add if it is a zero.
Can't skip the subtract since you have to do that to see if there was
a 1 or not.  But you can use it for subtract and compare at the same
time.  Set carry, subtract.  No borrow?  It fit, put a 1 in quotient
you already did subtract and have partial remainder so shift bringing
in next digit.  Borrow?  It was too big.  Put a zero in quotient.  Now
ADD test number back it.  You'll get your partial remainder back out,
 You get a carry back out since there was a borrow, everythings back
just like before you did the compare/subtract but you now know it won't
fit so shift and bring down your next digit.

  Now you know how to do a proper "reverse multiply" in binary that can
do any x into any x.  Do a few on paper and it will become remarkably
easy.

  Now lets see how fast someone can come up with a way to do a
 8 into 16 gives 8bit result (opposite of 8x8 to 16 bit mult) in ten
cycles!  ;)

  Sorry for the length of this post, at least it didn't go "Mooo"!

Alan