Patent ID: 7318080

Claim:
An apparatus for multiplying a first number by a second number, the apparatus comprising: first representation circuitry that represents the first number as a first set of two or more W-bit wide numbers, wherein W is an integer greater than or equal to 2; second representation circuitry that represents the second number as a second set of one or more W-bit wide numbers; pairing circuitry that pairs each of the W-bit wide numbers from the first set with each of the W-bit wide numbers from the second set; sub-partial product generation circuitry that generates a set of sub-partial products for each pair of W-bit wide numbers; combination forming circuitry that forms combinations of the sub-partial products such that each combination is representable by a W-bit wide lower partial product and a carry out term that has fewer than W bits; and combining circuitry that combines the W-bit wide lower partial products and the carry out terms to form the product of the first number and the second number.