Editing Multiplication algorithm (section)

===Usage in computers<span class="anchor" id="Shift and add"></span>===
Some [[Integrated circuit|chips]] implement long multiplication, in [[computer hardware|hardware]] or in [[microcode]], for various integer and floating-point word sizes.  In [[arbitrary-precision arithmetic]], it is common to use long multiplication with the base set to 2<sup>''w''</sup>, where ''w'' is the number of bits in a word, for multiplying relatively small numbers. To multiply two numbers with ''n'' digits using this method, one needs about ''n''<sup>2</sup> operations. More formally, multiplying two ''n''-digit numbers using long multiplication requires [[Bachmann-Landau notation|Θ]](''n''<sup>2</sup>) single-digit operations (additions and multiplications).

When implemented in software, long multiplication algorithms must deal with overflow during additions, which can be expensive. A typical solution is to represent the number in a small base, ''b'', such that, for example, 8''b'' is a representable machine integer. Several additions can then be performed before an overflow occurs.  When the number becomes too large, we add part of it to the result, or we carry and map the remaining part back to a number that is less than ''b''.  This process is called ''normalization''. Richard Brent used this approach in his Fortran package, MP.<ref>{{cite journal|first1=Richard P|last1=Brent|title=A Fortran Multiple-Precision Arithmetic Package. |doi=10.1145/355769.355775|journal=ACM Transactions on Mathematical Software|date=March 1978|volume=4|pages=57–70|citeseerx=10.1.1.117.8425|s2cid=8875817}}</ref>

Computers initially used a very similar algorithm to long multiplication in base 2, but modern processors have optimized circuitry for fast multiplications using more efficient algorithms, at the price of a more complex hardware realization.{{cn|date=March 2022}} In base two, long multiplication is sometimes called '''"shift and add"''', because the algorithm simplifies and just consists of shifting left (multiplying by powers of two) and adding. 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]].{{cn|date=March 2022}}

On currently available processors, a bit-wise shift instruction is usually (but not always) 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 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.
<syntaxhighlight lang="php">
 ((x << 2) + x) << 1 # Here 10*x is computed as (x*2^2 + x)*2
 (x << 3) + (x << 1) # Here 10*x is computed as x*2^3 + x*2
</syntaxhighlight>
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 <math>2^n</math> or <math>2^n \pm 1</math> often can be converted to such a short sequence.