# 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.