Multiplication algorithm: Difference between revisions

Revision as of 04:57, 16 September 2012

Revision as of 12:19, 23 September 2012

Line 209:

In base 2, multiplying by the single digit of the multiplier reduces to a simple series of [[logical AND]] operations. Each partial product is added to a running sum as soon as each partial product is computed. Most currently available microprocessors implement this or other similar algorithms (such as [[Booth encoding]]) for various integer and floating-point sizes in [[hardware multiplier]]s or in [[microcode]].

On currently available processors, a bit-wise shift instruction is faster than a multiply instruction and can be used to multiply (shift left) and divide (shift right) by powers of two. Multiplication by a constant and [[division (digital)algorithm#Division by a constant|division by a constant]] can be implemented using a sequence of shifts and adds or subtracts. For example, there are several ways to multiply by 10 using only bit-shift and addition.

<source lang="python">