The Karatsuba algorithm is a fast multiplication algorithm that uses a divide and conquer approach to multiply two numbers. The naive algorithm for multiplying two numbers has a running time of while this algorithm has a running time of . Being able to multiply numbers quickly is very important. Computer scientists often consider multiplication to be a constant time operation, and this is a reasonable simplification for smaller numbers; but for larger numbers, the actual running times need to be factored in, which is . The point of the Karatsuba algorithm is to break large numbers down into smaller numbers so that any multiplications that occur happen on smaller numbers. Karatsuba can be used to multiply numbers in all base systems (base-10, base-2, etc.).
The naive way to multiple numbers is commonly taught in elementary school.
Here’s the naive multiplication algorithm to multiply two -bit numbers, and that are in base .
Divide each number into two halves, the high bits and the low bits
Multiply the two numbers together:
These formulas describe what is going on in the image above--the familiar grade-school way of multiplying numbers. This has four multiplications: , , , and which has a running time of .
Let's use this method to multiply the base-10 numbers and
The Karatsuba algorithm decreases the number of subproblems to three and ends up calculating the product of two -bit numbers in time--a vast improvement over the naive algorithm.
To multiply two -bit numbers, and , the Karatsuba algorithm performs three multiplications and a few additions, and shifts on smaller numbers that are roughly half the size of the original and .
Here’s how the Karatsuba method works to multiply two -bit numbers and which are in base .
Create the following three subproblems where represents the high bits of the number and represents the lower bits:
This only requires three multiplications and has the recurrence Karatsuba can be applied recursively to a number until the numbers being multiplied are only a single-digit long (the base case).
Divide and conquer techniques come in when Karatsuba uses recursion to solve subproblems--for example, if multiplication is needed to solve for , , or before those variables can be used to solve the overall multiplication.
Perform the following multiplication using the Karatsuba method: .First, determine the value for step 1, --this will contain the high bits of and since and have four bits, and the left-most two are the high bits.
. Note, we will have to call the Karatsuba algorithm on since a multiplication is necessary to obtain the value (this time, a two-bit multiplication). Before we recurse, though, let’s find and .
contains the lower bits of each number since and have four bits, and the lower bits in this problem are the two right-most bits.
. Note, we will also have to recurse on to obtain the value.
Recall that .
. Now we are stuck and can’t simplify further until we have the values of and , so it is time to recurse.
We have Recall that Therefore, .
We have Since .
We have Since .
Now we can get the answer to the original problem as follows:
We have Plugging into , we get
Here is a Python implementation of the Karatsuba algorithm for base-10 numbers.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
To analyze the complexity of the Karatsuba algorithm, consider the number of multiplications the algorithm performs as a function of , . Recall that the algorithm multiplies together two -bit numbers. If for some , then the algorithm recurses three times on -bit number. The recurrence for this is
This takes care of the multiplications required for Karatsuba--now to consider the additions and subtractions. There are additions and subtractions required for the algorithm. Therefore, the overall recurrence for the Karatsuba algorithm is
Using the master theorem on the above recurrence yields that the running time of the Karatsuba algorithm is
The Schönhage–Strassen algorithm and the Toom–Cook algorithm are other popular integer multiplication algorithms. The Toom-Cook algorithm is faster, more generalized version of the Karatsuba algorithm that runs in . The Schönhage–Strassen algorithm is faster than both Karatsuba and Toom-Cook for very large on the order of and runs in .
- Demaine, E., Indyk, P., & Kellis, M. Karatsuba’s Algorithm. Retrieved May 29, 2016, from http://courses.csail.mit.edu/6.006/spring11/exams/notes3-karatsuba
- Babai, L. Divide and Conquer: The Karatsuba–Ofman algorithm. Retrieved May 30, 2016, from http://people.cs.uchicago.edu/~laci/HANDOUTS/karatsuba.pdf
- , . Toom–Cook multiplication. Retrieved May 30, 2016, from https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication
- , . Schönhage–Strassen algorithm. Retrieved May 30, 2016, from https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm