No Subject

[lowry@xxxxxxxxxxxxxxxxx (Dave Lowry)]

MISC Readers,

Michael A. Losh asks about multiplication.

The problem I have with +* as implemented is that you can only multiply two
10 bit numbers to get a 20 bit result.  True, the 20 bit x 20 bit problem can
be broken into four subproducts, but then all the shifting and other
contortions required to get a 40 bit answer make +* no more attractive than
the traditional shift-and-add algorithms.

It would be nice to see a +* that worked on a 40 bit register, as in the
RTX chips.

Michael suggests table lookups for subproducts.  This is a very good idea
speed-wise, but still takes lots of transistors.

There exist multiplication algorithms that multiply 2 or more bits at a time
using the shift-and-add technique.  Booth multiplication has the cool property
of working for twos-complement numbers automagically!  No fussing with the
sign bits required.  Again, this pretty much requires a 40 bit accumulation
register.

I proposed the array of adders approach only because it would be easy to lay
out in OKAD.  It is indeed very expensive in gates.  I have done a test
design of an 8x8 multiplier in a Xilinx chip.  (A "math coprocessor" for
P21).  To do the full 20x20 would need a little more than 9000 Xilinx gates.
Note that Field Programmable Gate Array (Xilinx, ATT, etc.) gate counts tend
to be high due to routing considerations, etc., so that Chuck could
probably do this in far fewer on the bare silicon.  But it's still a lot of 
gates.

I think a good balance would be a Booth-type multiplication using a 40bit
accumulation register.

-Dave
lowry@src.honeywell.com

All opinions mine, etc.