Karatsuba Multiplication — 3rd Grade Math on Steroids

In an effort to fill in my knowledge gaps on algorithms and data structures, I recently started a Coursera class offered by Stanford on the subject.

The first programming assignment involved building a Karatsuba algorithm in the language of your choice to multiply two 64-digit numbers.

What is the Karatsuba Algorithm?

a classic divide and conquer algorithm

The algorithm takes two digits of n-length and recursively splits these digits into n/2 length until they are small enough to compute using long-hand (3rd grade) multiplication. Recursive algorithms are algorithms that can invoke themselves as a subroutine with a smaller input; in order to call the subroutine recursively, the inputs must be smaller than those in the previous call.

Given inputs x and y of n-length in some base B (e.g. base 10), the algorithm itself looks like this:

x = a* B^m + b 
y = c* B^m + d
x * y = B^m(ac) + B^m/2(ad+bc) + bd

Now, instead of multiplying 1234 x 5678 the long way, you can do this:

a = 12
b = 34
c = 56
d = 78
n = 4
base of 10
x * y = 10^n(ac) + 10^(n/2)(ad + bc) + bd
x * y = 10⁴(672) + 10²(2840) + 2652
x * y = 7006652

The math seemed like magic and it made sense to me. But how to implement it in Ruby for a 64-digit number?


I started with the Karatsuba wiki to find the pseudocode for my own Ruby implementation:

procedure karatsuba(num1, num2)
if (num1 < 10) or (num2 < 10)
return num1*num2
/* calculates the size of the numbers */
m = max(size_base10(num1), size_base10(num2))
m2 = m/2
/* split the digit sequences about the middle */
high1, low1 = split_at(num1, m2)
high2, low2 = split_at(num2, m2)
/* 3 calls made to numbers approximately half the size */
z0 = karatsuba(low1,low2)
z1 = karatsuba((low1+high1),(low2+high2))
z2 = karatsuba(high1,high2)
return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)

If either of the number inputs are less than 10, they can be multiplied directly since the inputs only have 1 digit each. Next, we need to calculate the largest integer size in case the two integers are of different lengths and then find the approximate mid-point in each integer to find the location to split x into a + b. Once we have our smaller inputs a, b, c, and d, we make 3 calls to karatsuba recursively to compute ac, ad, bc, and bd. Once we have ac, ad, bc, and bd in the smallest units possible, we will return them in the final equation and pad the numbers with some base (in the pseudocode above, it assumes a number of base 10 (e.g. 100, 1000)).

After a few hours of typing and testing input cases, I have a working Ruby implementation!

def make_equal(num, mid, size)
string = num.to_s.rjust(size, '0')
return string.slice(0...mid).to_i, string.slice(mid..-1).to_i
end
def karatsuba(num1, num2)
return num1 * num2 if num1 < 10 || num2 < 10
size = [num1.to_s.length, num2.to_s.length].max
n = size/2
k = (size + 1) / 2

high1,low1 = make_equal(num1, k, size)
high2,low2 = make_equal(num2, k, size)

z0 = karatsuba(low1,low2)
z1 = karatsuba((low1 + high1), (low2 + high2))
z2 = karatsuba(high1,high2)
z3 = z1-z0-z2

return z2 * 10**(2*n) + ((z3) * 10**(n)) + z0
end

The purpose of the make_equal helper method is to create sub-strings of equal length, which means your input strings need to be modified to have equal length (e.g. num1 = 99, num2 = 1234) . The method will add padded leading zeros based on the max length of the two input integers and return two sub-integers based on a defined splitting point mid. For the purposes of the assignment, in which we were given two 64-digit integers, this was not an issue since both integers were of the same length.


In the process, I learned a new cool Ruby trick:

str.rjust(*args) (e.g. str.rjust(n, '0') where n = integer)

This Ruby String method allows you to compare your string to a desired string length. If your string is shorter than the integer, the method will return a new String of length integer with the string right-justified and padded with padstr, which can be anything you’d like. In my case, I used this to pad my shorter integer num1 string with leading zeros to make it even length with the longer integer num2 string.