Karazuba algorithm

The Karazuba algorithm is an algorithm for multiplying two large whole numbers . It was developed in 1960 by the 23-year-old Anatoly Alexejewitsch Karazuba (English Karatsuba, Russian Анатолий Алексеевич Карацуба ) and published in 1962.

If the number of bits of the two numbers and a Landau symbol designate , the algorithm is significantly faster than the school method with a runtime complexity of . This (and also its implicit transfer to the binary system in the form of the Russian pawn multiplication ) has a runtime complexity of . Karazuba's method became the model for the divide-and-conquer principle in computer science. For sufficiently large numbers, the Karazuba algorithm is slower than its generalizations, such as the Toom-Cook algorithm (1965) and the Schönhage-Strassen algorithm (1971), whose runtime complexity is and which, from the point of view of complexity theory, is the fastest algorithm for multiplication large until 2007, when Martin Fürer presented a further development with a (previously only theoretically) lower runtime complexity. ${\displaystyle n}$ ${\displaystyle O}$ ${\displaystyle O(n^{\log _{2}3}),\ \log _{2}3=1{,}5849\ldots ,}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O{\big (}n(\log n)\log(\log n){\big )}}$

Idea of ​​the algorithm

In the school method, multiplication causes an effort that grows with the square of the number of digits, while additions and shift operations , in which one multiplies by a power of the base of the place value system used, only require linear effort. The idea is to split the two numbers to be multiplied into two parts according to the divide-and-conquer principle, and to replace the multiplications with additions and shift operations as far as possible. The multiplication of the divided numbers results in three sub-terms, which are formed by four multiplications. These can be combined to form the overall result by shifting and adding operations. One of these terms is a sum of two products. This term can be written as the difference with a new product and the sum of the other two sub-terms. Overall, you save a partial multiplication. If you carry out this process recursively , you get a significantly more favorable running time than with the school method.

The algorithm in detail

The algorithm given here applies to natural numbers, but it can easily be generalized to whole numbers by taking their signs into account separately. The factors and are represented as tuples in the place value system . The value of is irrelevant: For example, in a computer with a multiplier for 32-bit wide numbers would be chosen. The examples below use decimal numbers . To recursion to be able to perform, the lengths of both Zifferntupel be a power of two with , and it was . This can always be achieved by using suitable leading zeros; This does not change anything essential in the run-time estimate carried out below. ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle b=2^{31}}$ ${\displaystyle n=1}$ ${\displaystyle 2^{m}}$ ${\displaystyle m>1}$ ${\displaystyle n:\,=2^{m-1}}$

The number tuples are therefore

${\displaystyle X=(x_{2n-1}\ldots x_{0})_{b}\ }$ and ${\displaystyle \ Y=(y_{2n-1}\ldots y_{0})_{b}.}$

Each digit tuple is now split into two length tuples . That gives the four numbers ${\displaystyle n}$

${\displaystyle X_{h}=(x_{2n-1}\ldots x_{n})_{b}\ }$and as well ${\displaystyle \ X_{l}=(x_{n-1}\ldots x_{0})_{b}\ }$

${\displaystyle Y_{h}=(y_{2n-1}\ldots y_{n})_{b}\ }$ and ${\displaystyle \ Y_{l}=(y_{n-1}\ldots y_{0})_{b}.}$

So is

${\displaystyle X=X_{h}b^{n}+X_{l}\ }$ and ${\displaystyle \ Y=Y_{h}b^{n}+Y_{l}.}$

When multiplied it results

${\displaystyle X\,Y=(X_{h}b^{n}+X_{l})(Y_{h}b^{n}+Y_{l})=X_{h}Y_{h}b^{2n}+(X_{h}Y_{l}+X_{l}Y_{h})\,b^{n}+X_{l}Y_{l}.}$

The term can now be put into another form that can be calculated more quickly: ${\displaystyle X_{h}Y_{l}+X_{l}Y_{h}}$

${\displaystyle X_{h}Y_{l}+X_{l}Y_{h}=(X_{h}Y_{h}+X_{h}Y_{l}+X_{l}Y_{h}+X_{l}Y_{l})-(X_{h}Y_{h}+X_{l}Y_{l})=(X_{h}+X_{l})(Y_{h}+Y_{l})-(X_{h}Y_{h}+X_{l}Y_{l}).}$

This results in the representation for the product

${\displaystyle X\,Y=X_{h}Y_{h}b^{2n}+{\big (}(X_{h}+X_{l})(Y_{h}+Y_{l})-(X_{h}Y_{h}+X_{l}Y_{l}){\big )}\,b^{n}+X_{l}Y_{l},}$

in which only the three "short" products

${\displaystyle P_{1}=X_{h}Y_{h},\ P_{2}=X_{l}Y_{l},\ P_{3}=(X_{h}+X_{l})(Y_{h}+Y_{l})}$

appear. They are calculated recursively and linked with simple shift and addition operations

${\displaystyle X\,Y=P_{1}b^{2n}+{\big (}P_{3}-(P_{1}+P_{2}){\big )}\,b^{n}+P_{2}.}$

Of the four possible products (of X with Y) X _h Y _h , X _h Y _l , X _l Y _h , X _l Y _l , the first P ₁ and the last P _{2 are used} directly in the result. The term from the sum of the two middle products can be formed as the sum of all products minus the first and last product. The sum of all four products can be generated using the newly introduced product P ₃ with just one multiplication.

Runtime analysis

A multiplication of two -digit numbers is traced back to three multiplications of two -digit numbers and four additions or subtractions of -digit numbers, possibly with carryovers and with two shifts. The time required for operations that are not multiplications is less than with one of the independent constants . Designates the total number of operations when multiplying two -digit numbers, then applies ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle cn}$ ${\displaystyle n}$ ${\displaystyle c}$ ${\displaystyle T(s)}$ ${\displaystyle s}$

${\displaystyle T(2n)\leq 3T(n)+cn,\ T(1)=1.}$

The first case of the Master's theorem that can be used here and provides the runtime complexity of The direct derivation with complete induction enables a more precise insight: ${\displaystyle a=3,\ b=2}$ ${\displaystyle f(n)\leq cn}$ ${\displaystyle O(n^{\log _{2}3})}$ ${\displaystyle T(n).}$

${\displaystyle T(2^{m})\leq 3^{m}T(1)+{\frac {c}{2}}2^{m}\sum \limits _{k=0}^{m-1}\left({\frac {3}{2}}\right)^{k}=3^{m}+c(3^{m}-2^{m})<(c+1)\,3^{m}.}$

Replacing with results in ${\displaystyle 2^{m}}$ ${\displaystyle n}$

${\displaystyle T(n)<(c+1)\,(2^{\log _{2}3})^{m}=(c+1)\,(2^{m})^{\log _{2}3}=(c+1)\,n^{\log _{2}3}.}$

Product forming example

Let the numbers to be multiplied be

${\displaystyle X=84\,232\,332\,233\ }$and . ${\displaystyle \ Y=1\,532\,664\,392}$

Since this is only about the illustration of the product reshaping, it is filled with leading zeros to the next even and equal length and not to a two-power length. This results in the number tuples

${\displaystyle X={\color {Blue}084\,232}\,{\color {OliveGreen}332\,233}}$ and ${\displaystyle Y={\color {Red}001\,532}\,{\color {Brown}664\,392}}$

of length , which are divided into four tuples of length : ${\displaystyle 2n=12}$ ${\displaystyle n=6}$

${\displaystyle X_{h}={\color {Blue}084\,232}}$and as well ${\displaystyle X_{l}={\color {OliveGreen}332\,233}}$

${\displaystyle Y_{h}={\color {Red}001\,532}}$ and ${\displaystyle Y_{l}={\color {Brown}664\,392}.}$

It applies

${\displaystyle X=X_{h}\cdot 10^{6}+X_{l}={\color {Blue}084\,232}\cdot 10^{6}+{\color {OliveGreen}332\,233}}$ and

${\displaystyle Y=Y_{h}\cdot 10^{6}+Y_{l}={\color {Red}001\,532}\cdot 10^{6}+{\color {Brown}664\,392}.}$

The products needed are

${\displaystyle P_{1}=X_{h}\cdot Y_{h}={\color {Blue}084\,232}\cdot {\color {Red}001\,532}=000\,129\,043\,424}$,

${\displaystyle P_{2}=X_{l}\cdot Y_{l}={\color {OliveGreen}332\,233}\cdot {\color {Brown}664\,392}=220\,732\,947\,336}$ and

${\displaystyle P_{3}=}$ ${\displaystyle \!(X_{h}+X_{l})\cdot (Y_{h}+Y_{l})=({\color {Blue}084\,232}+{\color {OliveGreen}332\,233})\cdot ({\color {Red}001\,532}+{\color {Brown}664\,392})=416\,465\ \cdot \ 665\,924=277\,334\,038\,660.}$

The algorithm would determine the products , and recursively. It remains to compose the result according to the above formula: ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$ ${\displaystyle P_{3}}$

${\displaystyle {\begin{array}{rll}X\cdot Y&=&P_{1}\cdot 10^{12}+{\big (}P_{3}-(P_{1}+P_{2}){\big )}\cdot 10^{6}+P_{2}\\&=&000\,129\,043\,424\cdot 10^{12}\\&&+{\big (}277\,334\,038\,660-(000\,129\,043\,424+220\,732\,947\,336){\big )}\cdot 10^{6}\\&&+220\,732\,947\,336.\end{array}}}$

While the school method requires 110 digit multiplications and 90 additions (without carry-overs), here there are 92 multiplications and 83 additions.

generalization

Instead of dividing the numbers into two parts, the numbers to be multiplied can also be broken down into more parts. With a clever linear combination of partial results, when decomposing into parts, multiplications on the smaller numbers are sufficient . Applied recursively, this procedure then leads to the Toom Cook algorithm . ${\displaystyle d+1}$ ${\displaystyle 2d+1}$

literature

• A. Karatsuba, Y. Ofman: Multiplication of Many-Digital Numbers by Automatic Computers. In: Soviet Physics-Doklady. 7, 1963, pp. 595-596 (English translation of the Russian original. In: Doklady Akad. Nauk SSSR. Volume 145, 1962, pp. 293-294).
• AA Karacuba: Calculations and the Complexity of Relationships. In: electron. Information processing Cybernetics. 11, 1975, pp. 603-606.
• AA Karatsuba: The Complexity of Computations. In: Proc. Steklov Inst. Math. 211, 1995, pp. 169-183 ( cs.ru PDF; English translation of the Russian original. In: Trudy Mat. Inst. Steklova. 211, 1995, pp. 186-202).
• DE Knuth: The Art of Computer Programming. Volume 2: Seminumerical Algorithms. Addison-Wesley Publ. Co., Reading, Mass., 1969, ISBN 0-201-89684-2 .

Web links

• Fast multiplication at i1.informatik.rwth-aachen.de
• Karatsuba Multiplication. on MathWorld
• DJ Bernstein: Multidigit multiplication for mathematicians. (PDF; 276 kB). Mathematical representation of various multiplication algorithms. Also handles the Karazuba algorithm.
• Karatsuba Multiplication on Fast Algorithms and the FEE.

References and comments

1. ↑ The English Lemma Fürer's algorithm contains some information on this.