Editing Multiplication algorithm (section)

==Long multiplication==
If a [[numeral system|positional numeral system]] is used, a natural way of multiplying numbers is taught in  schools
as '''long multiplication''', sometimes called '''grade-school multiplication''', sometimes called the '''Standard Algorithm''':
multiply the [[wikt:multiplicand|multiplicand]] by each digit of the [[wikt:multiplier|multiplier]] and then add up all the properly shifted results. It requires memorization of the [[multiplication table]] for single digits.

This is the usual algorithm for multiplying larger numbers by hand in base 10. A person doing long multiplication on paper will write down all the products and then add them together; an [[abacus]]-user will sum the products as soon as each one is computed.

===Example===
This example uses ''long multiplication'' to multiply 23,958,233 (multiplicand) by 5,830 (multiplier) and arrives at 139,676,498,390 for the result (product).
       23958233
 ×         5830
 ———————————————
       00000000 ( =  23,958,233 ×     0)
      71874699  ( =  23,958,233 ×    30)
    191665864   ( =  23,958,233 ×   800)
 + 119791165    ( =  23,958,233 × 5,000)
 ———————————————
   139676498390 ( = 139,676,498,390)

====Other notations====
In some countries such as [[Germany]], the above multiplication is depicted similarly but with the original product kept horizontal and computation starting with the first digit of the multiplier:<ref>{{Cite web |title=Multiplication |url=http://www.mathematische-basteleien.de/multiplication.htm |access-date=2022-03-15 |website=www.mathematische-basteleien.de}}</ref> 

 23958233 · 5830
 ———————————————
    119791165
     191665864
       71874699
        00000000
 ———————————————
    139676498390

Below pseudocode describes the process of above multiplication. It keeps only one row to maintain the sum which finally becomes the result. Note that the '+=' operator is used to denote sum to existing value and store operation (akin to languages such as Java and C) for compactness.

<syntaxhighlight lang="pascal" line>
multiply(a[1..p], b[1..q], base)                            // Operands containing rightmost digits at index 1
  product = [1..p+q]                                        // Allocate space for result
  for b_i = 1 to q                                          // for all digits in b
    carry = 0
    for a_i = 1 to p                                        // for all digits in a
      product[a_i + b_i - 1] += carry + a[a_i] * b[b_i]
      carry = product[a_i + b_i - 1] / base
      product[a_i + b_i - 1] = product[a_i + b_i - 1] mod base
    product[b_i + p] = carry                               // last digit comes from final carry
  return product
</syntaxhighlight>

===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.