Karatsuba Integer Multiplication Algorithm

The Karatsuba Integer Multiplication Algorithm is a really simple,fast recurrence based method to multiply two $n$ digit numbers.It was discovered by Anatoly Karastuba in 1960 and published in 1962. It is a good algorithm to start out within the Divide and Conquer algorithm and recursion for a beginner.

So why Karastuba?

Before we get into that question, let's focus/recap on some basic concepts.

A primitive operation is an operation of a the fundamental nature. It can be intuitively realised that these are namely two:- addition and multiplication. It can be easily realised that the larger the number of primitive operations( especially multiplication ) that are needed to be performed to produce an output, the more time it takes.

Now, consider a multiplication of two $4$ digit numbers, say $9999$ and
$9998$. It can be seen that to find a product and of these two numbers, we have two perform $2 \times \ 4^{2} \ = \ 32$ primitive multiplications accompanied with some primitive additions. It can now be realised that for any two $n$ digit numbers, the maximum primitive multiplications you need to carry out is $2n^{2}$ which is considerable amount of manual work for large values of $n$. Can we do better than this?

Well, we actually can using the Karatsuba Integer Multiplication Algorithm.

The Algorithm

Step 1 :- Write the numbers $X$ and $Y$ which are to multiplied in the form :-

$X \ = \ 10^{\frac{n}{2}} \times a \ + \ b$ and $Y \ = \ 10^{\frac{n}{2}} \times c \ + \ d$

where $n$ is the number of digits in the number $X$ or $Y$. If $n$ is an odd number say $9$ , you can raise $10$ to the power $5$ as an optimal value, however any $n$ works just fine.

Step 2:- $X \times Y \ = \ 10^{n} \times ac \ + \ 10^{\frac{n}{2}} \times (ad \ + \ bc) \ + \ bd$

Step 3:- Recursively calculate $ac$ and $bd$ if the multiplicands are of a decent order say $10^{5}$. You
might want to use the Grade school algorithm instead here if the order is less than that.

Step 4:- Recursively calculate $( a \ + \ b) \times \ ( c \ + \ d)$ (again if the order is decent enough) and then subtract $ad$ and $bd$ from it. This saves you from an extra work of calculating $ad$ and $bc$ seperately. Now do the remaining addition to get your product.

Now for our example, we consider the same multiplication prior stated i.e.:- of $9999$ and $9998$.

Let $a \ = \ 99$ , $b \ = \ 99$ , $c \ = \ 99$ and $d \ = \ 98$. $n$ here = $4$

Step 1 :- $ac$= $9801$ and $bd$ = $9702$

Step 2 :- $( a \ + \ b) \times \ ( c \ + \ d)$ = $39006$. Subtract $ac$ and $bd$ = $19503$

Step 3 :- $9999 \times \ 9998$ = $10^{4} \times \ 9801 \ + \ 10^{2} \times \ 19503 \ + \ 9702$ = $99970002$

Note that Karatsuba Integer Multiplication Algorithm only works on positive integers and if you want to implement it for negative numbers, you will need to make some obvious tweaks.