Shift and Add
Historically, computers used a "shift and add" algorithm for multiplying small integers. Both base 2 long multiplication and base 2 peasant multiplication reduce to this same algorithm. 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 multipliers 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 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.
((x << 2) + x) << 1 # Here x*10 => x* (x << 3) + (x << 1) # Here x*10 => x*In some cases such sequences of shifts and adds or subtracts will outperform hardware multipliers and especially dividers. A division by a number of the form or often can be converted to such a short sequence.
These types of sequences have to always be used for computers that do not have a "multiply" instruction, and can also be used by extension to floating point numbers if one replaces the shifts with computation of 2*x as x+x, as these are logically equivalent.
Read more about this topic: Multiplication Algorithm
Famous quotes containing the word shift:
“The term preschooler signals another change in our expectations of children. While toddler refers to physical development, preschooler refers to a social and intellectual activity: going to school. That shift in emphasis is tremendously important, for it is at this age that we think of children as social creatures who can begin to solve problems.”
—Lawrence Kutner (20th century)