Paul H. Dietz wrote:

>      Consider (A - B)^2 = A^2 + B^2 - 2AB
>
>      so AB = (A^2 + B^2 - [A-B]^2)/2
>
>      Since 101 > A > B, a small lookup table will suffice for all the
>      squares. (Note that A - B > 101 too!)


Actually along these same lines, you can do something like this:

let A = u*16 + v
    B = x*16 + y

We know A & B are 8-bit (or actually 7-bit) variables, so the
lower case variables u,v and x,y are the 4-bit hexadecimal digits
of A and B.

 A * B = (u*16+v) * (x*16+y)
       = u*x*256 + (u*y + v*x)*16 + v*y

The middle term can be manipulated to give this expression:
(u-v)*(y-x) = u*y - u*x - v*y + x*v
or
u*y + v*x = (u-v)*(y-x) + u*x + v*y
substistute back into the A*B expression

 A * B = u*x*256 + ((u-v)*(y-x) + u*x + v*y)*16 + v*y

Now while this may appear more complicated, note that only
three multiplications are required: u*x, v*y, and (u-v)*(y-x).
The first one is a 3-bit by 3-bit while the other two are
4-bit by 4-bit multiplications.

I haven't attempted to code this, but here are some ideas
to implement 4-bit by 4-bit multiplication (actually this
is a variation of something Andy posted a looong time ago
for squaring a 4-bit variable).

multiply the two 4-bit variables s and t:

    swapf   s,f    ;place s in the upper nibble
    clrw           ;result will go here
    clrc           ;
    btfsc   t,0
     addwf  s,w
    rrf     s,f

    btfsc   t,1
     addwf  s,w
    rrf     s,f

    btfsc   t,2
     addwf  s,w
    rrf     s,f

    btfsc   t,3
     addwf  s,w
    rrf     s,f

But weighing in at a hefty 15 cycles excludes this approach
from competing with the other versions.


The real benefit of this approach (other than attempting to
get free beer) is for multi-digit multiplications for processors
with built in multipliers. For example, if your processor has
a 16-bit multiplier and you want to multiply two 32-bit numbers,
then you can use this trick to reduce the multiplication to
three 16-bit multiplities plus five or so additions.

____________________________________

There's yet another way to optimitize the multiplication. The
challenge's rules state that the two numbers are in the range of 0-100.
Take a look at the binary representation of the last few numbers in
the range:

         76543210
  100    01100100
   99    01100011
   98    01100010
   97    01100001
   96    01100000
   95    01011111

If bits 5 and 6 are set, then bits 4 and 3 are clear. This information
could be used to turn the 7-bit by 7-bit multiplication into a 7-bit
by 5-bit multiplication for numbers less than 96 or into a 7-bit
by 3-bit multiplication for numbers between 96 and 100. It's true
there is some extra incurred overhead, but perhaps some free-time
wielding, enterprising, thirsty programmer is willing to take a hack
at it.

Scott
--
                                 __    /_
  I buy pizza instead of gas,    \      >
  and drink free beer.        (*)/(*)   o