# Need help figuring out simple multiplication hardware

As a part of my Computer Organization course, I need write to write a simple program (in C) that mics the work of "refined multiplication hardware" just like one shown in "Computer Organization and Design", by D. A. Patterson and J. L. Hennessy. Picture is attached.

I have a hard time understanding how this multiplier works (book has very little explanation) and and if it works with signed numbers(2's complement)

• With enough half-adders and barrel shifters in series, you can build a multiplier circuit with single-cycle throughput (but probably higher latency, given the depth.) Commented Mar 9, 2012 at 3:59

## 1 Answer

That looks like a classic shift-and-add type multiplier. A proper explanation would require a lot of diagrams, which sadly I can't provide at the moment. In a nutshell, if you are multiplying A times B, you start with an 'accumulator' register set to zero. Then you put A in a shift register and iteratively do the following: shift A left one place and look at the bit that falls out; if it's a '1', then add B to the accumulator, otherwise, don't add B. If there are any more bits remaining in A, you shift the accumulator left one place and repeat. If A and B are 32 bit values, there will be 32 iterations of this shifting and accumulating. Note also that since 32 shifts will be involved, the accumulator has to be 64 bits, to accommodate the result.

An optimization that you sometimes see is to use the high 32 bits of the accumulator to hold the value of A; by the time any given bit in the accumulated product is needed, the remaining piece of the value of A will have been shifted out of the way. This just cuts down on the storage needed in implementation, but conceptually the same math is carried out.

I may have flubbed a detail in that hasty explanation, but the basic gist of it should be there.

• Although multipliers are often drawn with a two-part shifter for the product as shown, it's worth noting that on the first step of the multiplication, the multiplier gets the first bit of the multiplicand and yields the first bit of the product. On the next step, it gets the second bit of the multiplicand and yields the second bit of the product. One could design a device which could multiply any size number by an N-bit number by feeding in the arbitrary-sized number, LSB first, and clocking out bits of the result (end by clocking in N zeroes and reading out the last N bits). Commented Feb 27, 2012 at 2:11
• I wonder why I've never seen any CPU with such a device built in? I've seen things like an 8-bit micro with a 16x16->32 multiplier which takes a minimum of 24 cycles to load values and retrieve results; performing extended precision maths (such as for RSA crypto) would be much faster with a 32x1 summing multiplier and a bus-interfaced shifter, than with the 16x16->32 hardware multiplier, even though the former would almost certainly represent less circuitry. Commented Feb 27, 2012 at 2:16
• +1. You might also link to pages that go into more detail, such as Massmind: "Novel Methods of Integer Multiplication and Division". Commented Mar 1, 2015 at 6:48