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 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. ... This article is about the calculator. ... 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 ------------- -------------------- 139,676,498,390 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. ... Portrait of Fibonacci, probably not authentic Leonardo of Pisa or Leonardo Pisano (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. 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 1|__0|__5|__5|__5|__0|__0|__5|__5|_ |1 |2 |7 |4 |6 |1 |2 |2 | 8 2|__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 9 0 

Peasant or binary multiplication

Main article: Peasant multiplication Peasant multiplication is an old algorithm for 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. 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 too busy to memorize the multiplication tables required by long multiplication. The algorithm was also in use in ancient Egypt. Flowcharts are often used to represent algorithms. ... Peasant multiplication is an old algorithm for 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 no 2915 47916466 1457 95832932 728 191665864 no 364 383331728 no 182 766663456 no 91 1533326912 45 3066653824 22 6133302648 no 11 12266615296 5 24533230592 2 49066461184 no 1 98132922368 ------------ 139676498390 

Multiplication algorithms for computer algebra

Karatsuba multiplication

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. To multiply two n-digit numbers x and y represented in base W, where n is even and equal to 2m (if n is odd instead, or the numbers are not of the same length, this can be corrected by adding zeros at the left end of x and/or y), we can write 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. ...

x = x₁ W^m + x₂

y = y₁ W^m + y₂

with m-digit numbers x₁, x₂, y₁ and y₂. The product is given by

xy = x₁y₁ W^2m + (x₁y₂ + x₂y₁) W^m + x₂y₂

so we need to quickly determine the numbers x₁y₁, x₁y₂ + x₂y₁ and x₂y₂. The heart of Karatsuba's method lies in the observation that this can be done with only three rather than four multiplications:

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

If T(n) denotes the time it takes to multiply two n-digit numbers with Karatsuba's method, then we can write

T(n) = 3 T(n/2) + cn + d

for some constants c and d, and this recurrence relation can be solved, giving 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. In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...

An Objective Caml implementation

 (* Decomposition of the numbers into arrays *) let decomposition10 a= let rec log10 a= if a<10 then 1 else 1+(log10 (a/10)) in let lga=log10 a in let resultat=Array.create (lga) 0 in let rec decomp_aux a i= if a=0 then () else begin let b=a/10 in resultat.(i)<-(a-10*b); decomp_aux b (i+1) end in decomp_aux a 0; resultat;; (* Power function, defined recursively *) let rec ( ** ) nb pb= if pb=0 then 1 else nb*(nb**(pb-1));; (* Gives both arrays the same length *) let equilibre vecta vectb= let pluslong=max (Array.length vecta) (Array.length vectb) in let m=Array.make_matrix 2 pluslong 0 in for i=0 to pluslong-1 do begin try m.(0).(i)<-vecta.(i) with _->m.(0).(i)<-0; end; begin try m.(1).(i)<-vectb.(i) with _->m.(1).(i)<-0; end done; m.(0),m.(1);; (* Karatsuba multiplication function *) let karatsuba a b= let decompa0=decomposition10 a and decompb0=decomposition10 b in let decompa,decompb=equilibre decompa0 decompb0 in let rec karatsuba_aux xi xj yi yj= if xi=xj && yi=yj then decompa.(xi)*decompb.(yi) else begin let x1y1=karatsuba_aux xi ((xi+xj)/2+1) yi ((yi+yj)/2+1) and x2y2=karatsuba_aux ((xi+xj)/2) xj ((yi+yj)/2) yj and x1y2=karatsuba_aux xi ((xi+xj)/2+1) ((yi+yj)/2) yj and x2y1=karatsuba_aux ((xi+xj)/2) xj yi ((yi+yj)/2+1) and m2=(xi-xj)/2+1 in x1y1*(10**(2*m2))+(x1y2+x2y1)*(10**m2)+x2y2 end in karatsuba_aux (Array.length decompa -1) 0 (Array.length decompa-1) 0;; 

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 complexity to O(n^1+e) for any e > 0, the overhead also grows. Using more parts eventually comes up against the law of diminishing returns, and the method of Fourier transforms is typically faster. In economics, diminishing returns is the short form of diminishing marginal returns. ...

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 For the computer science usage see convolution (computer science) . 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... 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 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 represents the imaginary unit, i2 = −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 powers of variables are combined using (only) addition, subtraction, and multiplication. ...

See also

• Strassen algorithm

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