Karatsuba algorithm

Karazuba the algorithm is an algorithm for multiplying two large integers. It was founded in 1960 by the 23 -year-old Anatoly Alexeyevich Karazuba (English Karatsuba, Russian Анатолий Алексеевич Карацуба ) developed and published in 1962. Specifies the number of bits of the two numbers and a Landau symbol, the algorithm with a running time complexity of is significantly faster than the school method. These ( and their implicit transfer to the binary system in the form of the Russian peasant multiplication ) has a runtime complexity of. The method of Karazuba became the model for the divide-and- conquer principle in computer science. For sufficiently large numbers of Karazuba algorithm is slower than its generalizations, such as the Toom - Cook algorithm (1965 ) and the Schönhage - Strassen algorithm (1971 ), is its running time complexity and the great from the perspective of complexity theory as the fastest algorithm for multiplying integers was, until 2007 Martin Furer a development with a (so far only in theory) lower runtime complexity is presented.

Idea of the algorithm

Multiply caused in the school method quadratic time, while additions and shift operations, which is multiplied by a power of the radix of the value system in use, only need linear effort. The idea is to split the two numbers to be multiplied into two parts by the divide-and -conquer principle, and to possibly replace the multiplications by additions and shift operations. The multiplying the split figures shows three partial terms which are formed by four multiplications. These can be assembled by shifting and addition operations to the overall result. 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 subterms. Altogether one saves a part of multiplication. If this procedure is recursively, we obtain a much better life than the school method.

The algorithm in detail

The algorithm given here applies to natural numbers, it can be easy but also to whole numbers generalize by their signs are taken into account separately. The factors and are shown in the place value system to the base as a tuple. The value of is irrelevant: Approximately in a computer with a multiplier for 32 -bit numbers would be selected. The examples below use decimal numbers. In order to perform the recursion to, the lengths of both Zifferntupel be with a power of two, and it was. This is always achievable by suitable leading zeros; at the bottom conducted runtime estimation by changes nothing essential.

The Zifferntupel so be

Each Zifferntupel is now split into two tuple of length. This provides the four numbers

In order to

Multiplied out results

The term can now bring in another, here faster computable form:

This produces for the product presentation

In which only the three "short" products

Appear. Calculated recursively and linked to a simple shift and addition operations they provide

Runtime Analysis

A multiplication of two - digit numbers is attributed to three multiplications of each two - digit numbers and four additions or subtractions - digit numbers possibly with carries and two shifts. The time required for the operations, which are not multiplications is smaller than a constant independent. Refers to the total number of operations in the multiplication of two -digit numbers, then applies

The applicable here first case of the master theorem, supplying a runtime complexity of the direct derivation by induction allows a closer look:

Replacing by then yields

Example of product transformation

The numbers to be multiplied are

Because it 's all about the illustration of the forming product here, it is filled with leading zeros to the nearest even and equal length and not on a two potency length. Thus, the result Zifferntupel

The length of which are divided into four tuple of length

It is

The products needed are

The algorithm would be the products and determine recursively. It is the result of the above formula to assemble:

While the school method requires 110 multiplications and 90 additions digits (no transfers ), there are 92 multiplications and 83 additions here.

Generalization

Instead of two parts, the numbers to be multiplied are divided into more parts. By skillful linear combination of partial results are then sufficient for decomposition into parts multiplications on the smaller numbers. Recursively applied this method then leads to the Toom - Cook algorithm.