A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have been around since the advent of the decimal system. Flowcharts are often used to represent algorithms. ... In mathematics, multiplication is an arithmetic operation which is the inverse of division, and in elementary arithmetic, can be interpreted as repeated addition. ...

Long multiplication

If you use a positional numeral system, a natural way of multiplying numbers is taught in grade schools as long multiplication: multiply the multiplicand by each digit of the multiplier and then add up all the properly shifted results. This has the advantage of being fairly accurate when performed by a skilled person, and the disadvantages that the method is complex, requires memorization of a multiplication table or in earlier times possession of a set of Napier's bones, neat penmanship and mental focus, not necessarily all present in young students. A numeral is a symbol or group of symbols that represents a number. ... In mathematics, multiplication is an arithmetic operation which is the inverse of division, and in elementary arithmetic, can be interpreted as repeated addition. ... There are several things called a Multiplier. ... In mathematics, a multiplication table is a mathematical table used to define a multiplication operation for an algebraic system. ... Napiers bones are an abacus invented by John Napier for calculation of products and quotients of numbers. ...

Humans usually use this algorithm in base 10, computers in base 2 (where multiplying by the single digit of the multiplier reduces to a simple series of logical and operations). Humans will write down all the products and then add them together; computers (and abacus operators) will sum the products as soon as each one is computed. Some chips implement this algorithm for various integer and floating-point sizes in hardware or in microcode. To multiply two numbers with n digits using this method, one needs about n² operations. More formally: the time complexity of multiplying two n-digit numbers using long multiplication is Ο(n²). Logical conjunction (usual symbol and) is a logical operator that results in true if both of the operands are true. ... An abacus is a calculation tool, often constructed as a wooden frame with beads sliding on wires. ... Hardware is the general term that is used to describe physical artifacts of a technology. ... A microprogram is a program consisting of microcode that controls the different parts of a computers central processing unit (CPU). ... It has been suggested that Landau notation be merged into this article or section. ...

Example

 23958233 5830 × ------------ 00000000 (= 0 × 23,958,233) 71874699 (= 3 × 239,582,330) 191665864 (= 8 × 2,395,823,300) 119791165 (= 5 × 23,958,233,000) ------------ 139676498390 (= 139,676,498,390) 

Lattice multiplication

Lattice multiplication is algorithmically equivalent to long multiplication. It requires the preparation of a lattice (a grid drawn on paper) which guides the calculation and separates all the multiplications from the additions. It was introduced to Europe in 1202 in Fibonacci's Liber Abaci. 3 + 2 with apples, a popular choice in textbooks Addition is the basic operation of arithmetic. ... // Events August 1 - Arthur of Brittany captured in Mirebeau, north of Poitiers Beginning of the Fourth Crusade. ... Leonardo of Pisa (Pisa, c. ... Liber Abaci (1202) is an historic book on arithmetic by Leonardo of Pisa, known later by his nickname Fibonacci. ...

As shown in the example, the multiplicand and multiplier are written above and to the right of a lattice.

• During the multiplication phase, the lattice is filled in with two-digit products of the corresponding digits labelling 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.

Example

 2 3 9 5 8 2 3 3 +---+---+---+---+---+---+---+---+- |1 /|1 /|4 /|2 /|4 /|1 /|1 /|1 /| | / | / | / | / | / | / | / | / | 5 01|/ 0|/ 5|/ 5|/ 5|/ 0|/ 0|/ 5|/ 5| +---+---+---+---+---+---+---+---+- |1 /|2 /|7 /|4 /|6 /|1 /|2 /|2 /| | / | / | / | / | / | / | / | / | 8 02|/ 6|/ 4|/ 2|/ 0|/ 4|/ 6|/ 4|/ 4| +---+---+---+---+---+---+---+---+- |0 /|0 /|2 /|1 /|2 /|0 /|0 /|0 /| | / | / | / | / | / | / | / | / | 3 17|/ 6|/ 9|/ 7|/ 5|/ 4|/ 6|/ 9|/ 9| +---+---+---+---+---+---+---+---+- |0 /|0 /|0 /|0 /|0 /|0 /|0 /|0 /| | / | / | / | / | / | / | / | / | 0 24|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0| +---+---+---+---+---+---+---+---+- 26 15 13 18 17 13 09 00 

 01 02 17 24 26 15 13 18 17 13 09 00 ============= 139676498390 

 = 139,676,498,390 

Peasant or binary multiplication

Main article: Peasant multiplication

In base 2, long multiplication reduces to a nearly trivial operation. For each '1' bit in the multiplier, shift the multiplicand an appropriate amount and then sum the shifted values. Depending on computer processor architecture and choice of multiplier, it may be faster to code this algorithm using hardware bit shifts and adds rather than depend on multiplication instructions, when the multiplier is fixed and the number of adds required is small. It has been suggested that this article or section be merged with Ancient Egyptian multiplication. ... There are several things called a Multiplier. ... In mathematics, multiplication is an arithmetic operation which is the inverse of division, and in elementary arithmetic, can be interpreted as repeated addition. ...

This algorithm is also known as Peasant multiplication, because it has been widely used among those who are unschooled and thus have not memorized the multiplication tables required by long multiplication. The algorithm was also in use in ancient Egypt. Flowcharts are often used to represent algorithms. ... It has been suggested that this article or section be merged with Ancient Egyptian multiplication. ... In mathematics, a multiplication table is used to define a multiplication operation for an algebraic system. ...

On paper, write down in one column the numbers you get when you repeatedly halve the multiplier, ignoring fractions; in a column beside it repeatedly double the multiplicand. Cross out each row in which the first number is even, and add the remaining numbers in the second column to obtain the product. There are several things called a Multiplier. ... In mathematics, multiplication is an arithmetic operation which is the inverse of division, and in elementary arithmetic, can be interpreted as repeated addition. ...

The main advantages of this method are that it can be taught in the time it takes to read aloud the preceding paragraph, no memorization is required, and it can be performed using tokens such as poker chips if paper and pencil are not available. It does however take more steps than long multiplication so it can be unwieldy when large numbers are involved.

Example

 5830 23958233 2915 47916466 1457 95832932 728 191665864 364 383331728 182 766663456 91 1533326912 45 3066653824 22 6133302648 11 12266615296 5 24533230592 2 49066461184 1 98132922368 ------------ 139676498390 

Multiplication algorithms for computer algebra

Karatsuba multiplication

Main article: Karatsuba algorithm

For systems that need to multiply numbers in the range of several thousand digits, such as computer algebra systems and bignum libraries, long multiplication is too slow. These systems may employ Karatsuba multiplication, which was discovered in 1962. The heart of Karatsuba's method lies in the observation that two-digit multiplication can be done with only three rather than the four multiplications classically required: The Karatsuba multiplication algorithm, a technique for quickly multiplying large numbers, was discovered by Karatsuba and Ofman in 1962. ... A computer algebra system (CAS) is a software program that facilitates symbolic mathematics. ... A bignum package in a computer or program allows internal representation of very large integers, rational numbers, decimal numbers, or floating-point numbers (limitted only by available memory), and provides a set of arithmetic operations on such numbers. ...

1. compute x₁y₁, call the result A
2. compute x₂y₂, call the result B
3. compute (x₁ + x₂)(y₁ + y₂), call the result C
4. compute C - A - B; this number is equal to x₁y₂ + x₂y₁.

To compute these three products of m-digit numbers, we can employ the same trick again, effectively using recursion. Once the numbers are computed, we need to add them together, which takes about n operations. A Sierpinski triangle —a confined recursion of triangles to form a geometric lattice. ...

Karatsuba multiplication has a time complexity of Θ(n^ln(3)/ln(2)). The number ln(3)/ln(2) is approximately 1.585, so this method is significantly faster than long multiplication. Because of the overhead of recursion, Karatsuba's multiplication is slower than long multiplication for small values of n; typical implementations therefore switch to long multiplication if n is below some threshold.

Toom-Cook

Another method of multiplication is called Toom-Cook or Toom3. The Toom-Cook method splits each number to be multiplied into multiple parts. Karatsuba is a special case of Toom-Cook using two parts. A three-way Toom-Cook can do a size-N³ multiplication for the cost of five size-N multiplications, improvement by a factor of 9/5 compared to the Karatsuba method's improvement by a factor of 4/3. Toom-Cook, sometimes known as Toom-3, is a method of multiplying two large integers. ...

Although using more and more parts can reduce the time spent on recursive multiplications further, the overhead from additions and digit management also grows. For this reason, the method of Fourier transforms is typically faster for numbers with several thousand digits, and asymptotically faster for even larger numbers.

Fourier transform methods

The idea, due to Strassen (1968), is the following: We choose the largest integer w that will not cause overflow during the process outlined below. Then we split the two numbers into groups of w bits : Volker Strassen is a German mathematician. ... In computer programming, an integer overflow is an anomalous condition which may cause a buffer overflow, resulting in a computer security risk where adjacent, valid program control data may be overwritten, permitting the execution of arbitrary, and potentially harmful code. ...

and

We can then say that

by setting b_j=0 for j > m, k=i+j and {c_k} as the convolution of {a_i} and {b_j}. Using the convolution theorem ab can be computed by In mathematics and, in particular, functional analysis, convolution is a mathematical operator which takes two functions f and g and produces a third function that in a sense represents the amount of overlap between f and a reversed and translated version of g. ... In mathematics, the convolution theorem states that the Fourier transform of a convolution is the point-wise product of Fourier transforms. ...

1. Computing the fast Fourier transforms of {a_i} and {b_j},
2. Multiplying the two results entry by entry,
3. Computing the inverse Fourier transform and
4. Adding the part of c_k that is greater than 2^w to c_k+1

The fastest known method based on this idea was described in 1971 by Schönhage and Strassen (Schönhage-Strassen algorithm) and has a time complexity of O(n ln(n) ln(ln(n))). A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. ... Arnold Schönhage (born 1934) is a mathematician and computer scientist and Professor Emeritus at Rheinische Friedrich-Wilhelms-Universität, Bonn. ... Volker Strassen is a German mathematician. ... In mathematics, the Schönhage-Strassen algorithm is an asympotically fast method for multiplication of large integer numbers. ...

Applications of this algorithm includes GIMPS. The Great Internet Mersenne Prime Search, or GIMPS, is a collaborative project of volunteers, who use Prime 95 and MPrime, special open source software that can be downloaded from the Internet for free, in order to search for Mersenne prime numbers. ...

Using number-theoretic transforms instead of discrete Fourier transforms avoids rounding error problems by using modular arithmetic instead of complex numbers. The number-theoretic transform is similar to the discrete Fourier transform, but operates with modular arithmetic instead of complex numbers. ... In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, solve partial differential equations, and to perform other operations such as convolutions. ... A round-off error is the difference between the calculated approximation of a number and its exact mathematical value. ... Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... Wikibooks Algebra has more about this subject: Complex numbers In mathematics, a complex number is an expression of the form where a and b are real numbers, and i is a specific imaginary number, called the imaginary unit, with the property i 2 = −1. ...

Polynomial multiplication

All the above multiplication algorithms can also be expanded to multiply polynomials. In mathematics, a polynomial is an expression in which constants and variables are combined using only addition, subtraction, multiplication, and positive whole number exponents (raising to a power). ...

See also

• Binary numeral system
• Slide rule
• Strassen algorithm

The binary numeral system (base 2 numerals) represents numeric values using two symbols, typically 0 and 1. ... The slide rule (often nicknamed a slipstick) is a mechanical analog computer, consisting of calibrated strips, usually a fixed outer pair and a movable inner one, with a sliding window called the cursor. ... In the mathematical discipline of linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm used for matrix multiplication. ...

External links

• Multiplication Algorithms used by GMP