Multiplication Algorithms

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.

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''²).

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 Addition s.
It was introduced to Europe in 1202 in Fibonacci 's
Liber Abaci .

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

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.

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.

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.

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 System s 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 2''m'' (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

: ''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''^2''m'' + (''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:

# compute ''x''₁''y''₁, call the result ''A''
# compute ''x''₂''y''₂, call the result ''B''
# compute (''x''₁ + ''x''₂)(''y''₁ + ''y''₂), call the result ''C''
# 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.

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

T

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.

An Objective Caml implementation

Decomposition of the numbers into arrays ---)

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

end
in
decomp_aux a 0;
resultat;;

Power function, defined recursively ---)

--- ) nb pb=

(nb
--(pb-1));;

Gives both arrays the same length ---)

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 decompa0=decomposition10 a
and decompb0=decomposition10 b in
let decompa,decompb=equilibre decompa0 decompb0 in
let rec karatsuba_aux xi xj yi yj=

decompb.(yi) else

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

(10
--(2---m2))+(x1y2+x2y1)---(10
--m2)+x2y2

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.

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.

FOURIER TRANSFORM METHODS

The idea, due to during the process outlined below. Then we split the two numbers into groups of ''w'' bits :

a=\sum_{i=0}^m {2^{wi}a_i}

and

b=\sum_{j=0}^m {2^{wj}b_j}

We can then say that

ab=\sum_{i=0}^m \sum_{j=0}^m 2^{w(i+j)}a_i b_j = \sum_{k=0}^{2m} 2^{wk} \sum_{i=0}^m a_i b_{k-i} = \sum_{k=0}^{2m} 2^{wk} c_k

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
#Computing the Fast Fourier Transform s of {''a''_i} and {''b''_j},
#Multiplying the two results entry by entry,
#Computing the inverse Fourier transform and
#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''))).

Applications of this algorithm includes GIMPS .

Using Number-theoretic Transform s instead of Discrete Fourier Transform s avoids Rounding Error problems by using Modular Arithmetic instead of Complex Number s.

POLYNOMIAL MULTIPLICATION

All the above multiplication algorithms can also be expanded to multiply Polynomial s.

SEE ALSO

Strassen Algorithm

EXTERNAL LINKS

Multiplication Algorithms used by GMP

Information About

Multiplication Algorithms