Method in a computing system for performing a multiplication

Abstract

In a computing system a method for performing a multiplication of a first multiplicand and a second multiplicand is presented. The computing system includes a plurality of registers, an instruction decoder, an arithmetic logic unit, and a preshifter. The first multiplicand is divided into a plurality of equal length sections. Each section includes 'n' bits, where 'n' is an integer greater than one. The second multiplicand is placed in a first register from the plurality of registers. A second register from the plurality of registers is cleared to zero. For each section from the plurality of sections, starting with a first section containing high order bits of the first multiplication and proceeding to a last section of the first multiplicand containing low order bits of the first multiplicand the following three substeps. First, when the low order bit of a current section is a '1', the contents of the first register are added to the contents of the second register via the arithmetic logic unit. Second, for every other bit in the current section that is a '1', a shift-and-add operation is performed by shifting, via the preshifter, the contents of the first register by an amount equal to the number of bit places the bit is to the left of the low order bit of the current section and by adding, via the arithmetic logic unit, the preshifted contents of the first register to the contents of the second register. Third, for every section from the plurality of sections that does not contain low order bits of the first multiplicand, the contents of the first register 'n' bits are shifted to the left.