Patent attributes
A first number is multiplied by a second number, by representing the first number as a first set of one or more W-bit wide numbers, and representing the second number as a second set of one or more W-bit wide numbers. Each of the W-bit wide numbers from the first set is paired with each of the W-bit wide numbers from the second set. For each pair of W-bit wide numbers, a set of sub-partial products is generated. Combinations of the sub-partial products are formed 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. The W-bit wide lower partial products and the carry out terms are combined to form the product of the first number and the second number. The carry out term is advantageously representable by (W/2)+1 bits.
