Karatsuba Multiplication

From Algorithmist
Jump to: navigation, search

Karatsuba Multiplication is a faster algorithm for BigNum or BigInt multiplication that is still fairly simple to implement. Its runtime complexity is O(n^{{\lg 3}})\approx O(n^{{1.58}}), although it involves more additions and subtractions than the naive algorithm.

It is based on the clever observation that to find (ax+b)(cx+d) (which is acx^{2}+(ad+bc)x+bd), we need only three multiplications, while the naive method of multiplying them out would take four multiplications. The three multiplications are:

  1. ac
  2. bd
  3. (a+b)(c+d)=ac+bd+ad+bc

The coefficient of x, namely ad+bc can therefore be found by subtracting the results of the first two multiplications from that of the third, thereby saving us one multiplication.

What this means for BigNums is that given two integers m and n of about 2k digits each, we can write them as m=a10^{k}+b and n=c10^{k}+d (by taking a to be the integer formed by the first half of the digits of m, etc). Now, we can use the above observation to compute mn=(ac)10^{{2k}}+((a+b)(c+d)-ac-bd)10^{k}+bd. (Note that multiplying by a power of 10 (or in general, the base we are working with) simply consists of shifting the digits a certain number of places, as we are doing in the naive multiplication algorithm, too.) Thus, the time T(l) taken by this algorithm to multiply two integers of length k is T(k)=3T(k/2)+O(k), which gives a runtime of O(k^{{\lg 3}}).

Extensions of Karatsuba[edit]

In Karatsuba multiplication, we break the multiplicands into two parts. What happens if, say, we break them into three parts? This leads to the Toom-Cook 3-way multiplication algorithm, which has an asymptotic runtime of O(n^{{\log _{3}5}})\approx O(n^{{1.465}}). This is asymptotically faster than Karatsuba, but the algorithm requires more work to be done in post-processing after the recursive multiplications are done.

Obviously the idea can be extended to break the multiplicands into even more pieces, but at some point the amount of work needed to recover the actual digits outweighs the work saved in the clever formulation of the problem.