Content deleted Content added
→Fourier transform methods: note about using GF(2^mersenne_prime) |
|||
Line 206:
== 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 multiplier]]s or in [[microcode]].
| |||