One detail I'm glossing over for simplicity, is that I've assumed that n
is an even integer. Now, if n is an odd integer, you can
apply this exact same recursive approach to integer multiplication.
In the straightforward way, so if n was 9 then you would decompose one of these
input numbers into say the first five digits and the later four digits and you
would proceed in exactly the same way. Now the point of the expression star is
if we look at it despite being the product of just elementary algebra, it
suggests a recursive approach to multiplying two numbers.
If we care about the product Of X and Y, why not, instead, compute this expression
star, which involves only the products of smaller numbers, A, B, C and D.
You'll notice, staring at the expression star, there are 4 relevant products, each
involving a pair of these smaller numbers.
Namely AC, AD, BC, and BD . So why not compute each of those four
products recursively. After all, the inputs will be smaller.
And then once our four recursive calls come back to us with the answer, we can
formulate the rest of expression star in the obvious way.
We just pad a times c with n zeros at the end.
We add up a, d, and bc, using the grade school algorithm, and pad the result with
n over two zeros, and then we just sum up these returns, again using the grade
school addition, and algorithm. So the one detail missing, that I've
glossed over, required to turn this idea into a bonafide recursive algorithm,
would be to specify a base case. As I hope you all know, recursive
algorithms need a base case. If the input is sufficiently small, then
you just immediately compute the answer rather than recursing further.
Of course, recursive algorithms need a base case so they don't keep calling
themselves til the rest of time. So for integer multiplication, which the
base case, well, if you're given two numbers that have the just one digit
each. Then you just multiply them in one basic
operation and return the result. So, what I hope is clear at the moment is
that there is indeed a recursive approach to solving the integer multiplication
algorithm resulting in an algorithm which looks quite different than the one you
learned in third grade, but which nevertheless you could code up quite
easily in your favorite programming language.
Now, what you shouldn't have any intuition about is whether or not this is
a good idea or a completely crackpot idea.
Is this algorithm faster or slower than the grade school algorithm?
You'll just have to wait to find out the answer to that question.
Let's now refine this recursive algorithm, resulting in the full-blown
Karatsuba multiplication algorithm. To explain the optimization behind
Karatsuba multiplication, let's recall the expression we were calling star on
the previous slide. So, this just expressed the product of x
and y in terms of the smaller numbers a, b, c, and d.
In this straight forward recursive algorithm we made four recursive calls to
compute the four products which seemed necessary to value, to compute the
expression star. But if you think about it, there's really
only three quantities in star that we care about, the three relevant
coefficients. We care about the numbers ad and bc.
Not per se, but only in as much as we care about their sum, AD plus BC.
So this motivates the question, if there's only 3 quantities that we care
about, can we get away with only 3 rather than 4 recursive calls.
It turns out that we can and here's how we do it.