Multiplication algorithm

A multiplication algorithm is an algorithm to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Numerous algorithms are known and there has been much research into the topic.
The oldest and simplest method, known since antiquity as long multiplication or grade-school multiplication, consists of multiplying every digit in the first number by every digit in the second and adding the results. This has a time complexity of, where n is the number of digits. When done by hand, this may also be reframed as grid method multiplication or lattice multiplication. In software, this may be called "shift and add" due to bitshifts and addition being the only two operations needed.
In 1960, Anatoly Karatsuba discovered Karatsuba multiplication, unleashing a flood of research into fast multiplication algorithms. This method uses three multiplications rather than four to multiply two two-digit numbers. Done recursively, this has a time complexity of. Splitting numbers into more than two parts results in Toom–Cook multiplication; for example, using three parts results in the Toom-3 algorithm. Using many parts can set the exponent arbitrarily close to 1, but the constant factor also grows, making it impractical.
In 1968, the Schönhage–Strassen algorithm, which makes use of a Fourier transform over a modulus, was discovered. It has a time complexity of. In 2007, Martin Fürer proposed an algorithm with complexity. In 2014, Harvey, Joris van der Hoeven, and Lecerf proposed one with complexity, thus making the implicit constant explicit; this was improved to in 2018. Lastly, in 2019, Harvey and van der Hoeven came up with a galactic algorithm with complexity. This matches a guess by Schönhage and Strassen that this would be the optimal bound, although this remains a conjecture today.
Integer multiplication algorithms can also be used to multiply polynomials by means of the method of Kronecker substitution.

Long multiplication

If a 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 multiplicand by each digit of the 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 by 5,830 and arrives at 139,676,498,390 for the result.
23958233
× 5830
———————————————
00000000
71874699
191665864
+ 119791165
———————————————
139676498390

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:
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 for compactness.

multiply // Operands containing rightmost digits at index 1
product = // 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 += carry + a * b
carry = product / base
product = product mod base
product = carry // last digit comes from final carry
return product

Usage in computers

Some chips implement long multiplication, in 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^w, 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² operations. More formally, multiplying two n-digit numbers using long multiplication requires Θ single-digit operations.
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, 8b 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.
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. In base two, long multiplication is sometimes called "shift and add", because the algorithm simplifies and just consists of shifting left and adding. Most currently available microprocessors implement this or other similar algorithms for various integer and floating-point sizes in hardware multipliers or in microcode.
On currently available processors, a bit-wise shift instruction is usually faster than a multiply instruction and can be used to multiply and divide 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.

<< 1 # Here 10*x is computed as *2
+ # Here 10*x is computed as x*2^3 + x*2

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.

Algorithms for multiplying by hand

In addition to the standard long multiplication, there are several other methods used to perform multiplication by hand. Such algorithms may be devised for speed, ease of calculation, or educational value, particularly when computers or multiplication tables are unavailable.

Grid method

The grid method is an introductory method for multiple-digit multiplication that is often taught to pupils at primary school or elementary school. It has been a standard part of the national primary school mathematics curriculum in England and Wales since the late 1990s.
Both factors are broken up into their hundreds, tens and units parts, and the products of the parts are then calculated explicitly in a relatively simple multiplication-only stage, before these contributions are then totalled to give the final answer in a separate addition stage.
The calculation 34 × 13, for example, could be computed using the grid:

×	30	4
10	300	40
3	90	12

followed by addition to obtain 442, either in a single sum, or through forming the row-by-row totals
This calculation approach is also known as the partial products algorithm. Its essence is the calculation of the simple multiplications separately, with all addition being left to the final gathering-up stage.
The grid method can in principle be applied to factors of any size, although the number of sub-products becomes cumbersome as the number of digits increases. Nevertheless, it is seen as a usefully explicit method to introduce the idea of multiple-digit multiplications; and, in an age when most multiplication calculations are done using a calculator or a spreadsheet, it may in practice be the only multiplication algorithm that some students will ever need.

Lattice multiplication

Lattice, or sieve, multiplication is algorithmically equivalent to long multiplication. It requires the preparation of a lattice which guides the calculation and separates all the multiplications from the additions. It was introduced to Europe in 1202 in Fibonacci's Liber Abaci. Fibonacci described the operation as mental, using his right and left hands to carry the intermediate calculations. Matrakçı Nasuh presented 6 different variants of this method in this 16th-century book, Umdet-ul Hisab. It was widely used in Enderun schools across the Ottoman Empire. Napier's bones, or Napier's rods also used this method, as published by Napier in 1617, the year of his death.
As shown in the example, the multiplicand and multiplier are written above and to the right of a lattice, or a sieve. It is found in Muhammad ibn Musa al-Khwarizmi's "Arithmetic", one of Leonardo's sources mentioned by Sigler, author of "Fibonacci's Liber Abaci", 2002.

During the multiplication phase, the lattice is filled in with two-digit products of the corresponding digits labeling each row and column: the tens digit goes in the top-left corner.
During the addition phase, the lattice is summed on the diagonals.
Finally, if a carry phase is necessary, the answer as shown along the left and bottom sides of the lattice is converted to normal form by carrying ten's digits as in long addition or multiplication.