What They Didn’t Teach You in Elementary School — The Karatsuba Multiplication Algorithm

Image by author

The only way?

Most of us were taught the ‘standard’ way of multiplying two numbers which was to compute partial products, starting with the first digit of the second number with each of the digits of the first, then repeating this on other rows for the rest of the second number. Finally, we add up all these products to get the answer (yes, this also involves carrying/adding numbers and indenting each row:)

Voila —

     1234
   × 5678
   -------
     9872  (1234 × 8)
    8638   (1234 × 7, shifted one position to the left)
   7404    (1234 × 6, shifted two positions to the left)
+ 6170     (1234 × 5, shifted three positions to the left)
-------
  7006652

This is commonly referred to as long multiplication and in our example involved computing 4 products in each of the 4 rows, 4*4=16. Or written in terms of the length of the first number, n² total multiplies. For the astute among you, yes, I am ignoring the adding and carry operations as these constant terms are normally disregarded in algorithm analysis convention. You can see as the length of the input numbers grow so does the number of multiplies we must do.

number length= 2,4,8,16
number of multiplies = 4,16,64,256

Did you know there is a way to solve the above problem by only having to compute 3 partial products instead of 16?!

It’s called the Karatsuba Multiplication, let’s dive in-

Preprocessing: Equalize Lengths as a power of 2

First, if the lengths of the two numbers we are multiplying together, num1 and num2, are not already multiples of 2 and equal, we prepend leading zeros such as if we wanted to multiply the following :

12345 * 12

Would be reformatted as numbers both of length n=8:

00012345 * 00000012

This ensures that both numbers have the same length, and that said length is divisible by 2. The good news, as you can see, is this does not have any impact on the final answer but without it our algorithm wouldn’t work.

Splitting the Numbers

We then split num1 and num2 into halves and give them names- a,b,c,d:

For example, if num1 = 12 and num2 = 34 (length n = 2):
a = 1, b = 2 (12)
c = 3, d = 4 (34)

With this naming we could write any number as:
num1 becomes a * 10^(n/2) + b
num2 becomes c * 10^(n/2) + d

where n is the length of the number and 10^(n/2) is just 10 to the power of length of the numbers divided by 2.

1 * 10¹+ 2 = 12
3*10¹+4 = 34

A New Way of Multiplying Numbers

Using this notation, we can now express the product of these numbers by first just representing them this way:

(a * 10(n/2) + b) * (c * 10(n/2) + d)

Multiplying this out we get:

ac * 10n + (ad + bc) * 10(n/2) + bd ¹

Now comes a trick we can use to eliminate the need for computing ad and bc, since it turns out:

(a+b)(c+d) = ac + ad + bc + bd

Next, if we minus ac and bd from both sides we get our ad + bc:

(a+b)(c+d)-ac-bd = ad + bc

• note in my code below I will use the following to save space —
  q = ((a+b)(c+d)-ac-bd)

This allows us to find ad + bc by just reusing ac and bd along with computing only one product (the result of a+b with the result of c+d) as well as the trivial subtractions of ac and ad.

Substituting this for ad+bc into our expansion ¹ above gives us our final combining of terms to get our product.

ac * 10n + ((a+b)(c+d)-ac-bd) * 10(n/2) + bd ²

A Recursive Approach

In practice we recursively compute the 3 products — a*c, b*d, and (a+b)*(c+d )by first splitting the numbers in half to get a,b,c,d, computing a+b and c+d, then calling our same function recursively for each of the 3 products, passing each element as arguments.

This splitting and recursion continues until we reach a base case where our number lengths (n) = 1. At this point, we directly compute and return the pair-wise products num1*num2, which just involves multiplying single-digits :)

Combining The Results

As the recursion unwinds, we combine the products using addition and adding the appropriate # of zeros to the end of the numbers (the same as multiplying by powers of 10) using the already derived equation —

ac * 10n + ((a+b)(c+d)-ac-bd) * 10(n/2) + bd ²

which gives us our final result.

The Beauty of Karatsuba

The algorithm elegantly reduces the number of multiplications by breaking down the problem into smaller subproblems, a very common theme in many successful algorithms.

By recursively handling the product pairs, we avoid large multiplications and work with single-digit integers as well as keeping the total number of multiplications down.

The final combination step efficiently reconstructs the overall product. Notice that this approach is more efficient for large numbers, where the reduction in the number of multiplications significantly impacts the overall computation time as compared to the long multiplication method.

The Code

Here’s my Python implementation of Karatsuba multiplication, starting with two modules I use - numpy and time-

import numpy as np
import time

Next, is the function that checks and pads 0’s to the front of the numbers to make sure they are of equal lengths and said length is a multiple of two. Note that the log base 2 of a number is a whole number ( the is_integer() function returns true) only if the number is multiple of 2. This method ensures that any (positive) integers we pass in to multiply will work with the algorithm-

def validate_num_lengths(num1 : str, num2 : str) -> (str,str):
    nums = [num1,num2]
    # first make them the same length if they aren't by  prefixing 0's
    if not len(nums[0])==len(nums[1]): # we have to add 0's to the start so the n's match 
        max_idx = np.argmax([len(n) for n in nums]) # get which number is longer 
        nums[int(not max_idx)] = '0'*np.abs(len(nums[0]) - len(nums[1])) +  nums[int(not max_idx)] 
    added_len = 0
    while not np.log2(added_len+len(nums[0])).is_integer() : # add 0's until we get to a power of 2
        added_len +=1
    # prepend any needed 0's to make the length a power of 2
    nums[0] = '0'*added_len + nums[0] 
    nums[1] = '0'*added_len + nums[1]
    return nums[0],nums[1] 

Then we have the main recursive function that handles all the algorithm details we discussed above -

def recursive_mult_func(num1 : str, num2 : str) -> str:
    assert(len(num1) == len(num2))
    n = len(num1)
    if n==1:
        return str(int(num1) * int(num2))
    else:
        # split our integers in half and store them 
        a = num1[:int(len(num1)/2)]
        b = num1[int(len(num1)/2):]
        c = num2[:int(len(num2)/2)]
        d = num2[int(len(num2)/2):]
        # compute the product pairs recursively 
        ac = recursive_mult_func(a,c) # first 
        bd = recursive_mult_func(b,d) # second 
        a_plus_b = str(int(a)+int(b))
        c_plus_d = str(int(c)+int(d))
        # we must make sure these lenghth's are powers of two and equal as 
        # we did before since we added numbers which might have broken our 
        # divide by two symmetry 
        a_plus_b,c_plus_d = validate_num_lengths(a_plus_b,c_plus_d) 
        q  = recursive_mult_func(a_plus_b,c_plus_d) # third        
        # recursive calls have all returned with thair partial products
        # we have to minus out the ac and ad so we get our intended ad + bc value
        q = str(int(q)-int(ac) - int(bd)) # remember I said q would stand for this
        # finally main combine equation (2)
        return str(int(ac + '0'*n) + (int(q)*(10**int(n/2))) + int(bd)) 

Next, let’s package this all in a function that starts it off first by validating our numbers by front padding 0’s if needed, and then calling the main recursive function to do the work.

def Karatsuba_int_mult(num1 : str, num2 : str) -> str:
    #preprocess the numbers by adding 0's to the start so they will work in the algorithm, this will not affect the accuracy of the result 
    assert(int(num1)>0 and int(num2)>0)
    (num1,num2) = validate_num_lengths(num1, num2)
    return recursive_mult_func(num1,num2)

Now let’s test it out with our original long multiplication example from the start —

n1,n2 ='1234','5678' 
start_time = time.perf_counter() # perf_counter() is great for timing code
answer = Karatsuba_int_mult(n1,n2)
end_time = time.perf_counter()
elapsed_time = end_time - start_time
print(f"Karatsuba algoritm {n1}*{n2} = {answer} in {elapsed_time:.8f} sec")

Karatsuba algoritm 1234*5678 = 7006652 in 0.00025596 sec

This answer 7006652 matches what we got with the standard long division method, phew it worked :) ! Now let’s try a couple slightly bigger numbers that aren’t multiples of 2 nor equal length-

n1,n2 ='12581275871258712358712583712835781571','5825812858123858181283858123' 
start_time = time.perf_counter()
answer = Karatsuba_int_mult(n1,n2)
end_time = time.perf_counter()
elapsed_time = end_time - start_time
print(f"Karatsuba algoritm {n1}*{n2} = {answer} in {elapsed_time:.8f} sec")

Karatsuba algoritm 12581275871258712358712583712835781571*
5825812858123858181283858123 = 
73296158742382453051555870167553123776834362884303318314982051233 
in 0.00875321 sec

73296158742382453051555870167553123776834362884303318314982051233 ?!

Feel free to verify this is correct using the long multiplication method :)

Summary

I had so much fun writing this code and learning about this nifty way of doing multiplication. I hope you had a good time as well and found it as interesting as I did. Maybe, like me, this inspired you to look closer at the way you do things rather than only at the end result. Until next time and happy coding :)