# Parallel multiplication hardware

This picture is taken from Computer Organization and Design, Fourth Edition, David A. Patterson, John L. Hennessy. Sorry for the low resolution.

I cannot get my head around it. I can see why the bits to the right become lsb's in the product (Product1, Product0), but then the same thing is done for bits to the left. What about carries? Try this for Mcand and Mplier equal to 2^31. Then the correct Product63 is 0 (because the correct result is 2^62), but this design would set Product63 to 1, which is wrong!

Is there some deep mathematical property that could rescue this design, or am I correct to think that we need progressively wider adders to the left, as we go down the levels?

## Elaboration

To facilitate readers, I remind how we do pencil-and-paper multiplication (4 bit example).

            M3 M2 M1 M0 (Mcand)
* m3 m2 m1 m0 (Mplier)
-----------------------
a3 a2 a1 a0 (Mplier0*Mcand)
+        b3 b2 b1 b0    (Mplier1*Mcand)
+     c3 c2 c1 c0       (Mplier2*Mcand)
+  d3 d2 d1 d0          (Mplier3*Mcand)
-----------------------
p7 p6 p5 p4 p3 p2 p1 p0 (Product)