The Karatsuba Integer Multiplication Algorithm is a really simple,fast recurrence based method to multiply two 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 digit numbers, say and
. It can be seen that to find a product and of these two numbers, we have two perform primitive multiplications accompanied with some primitive additions. It can now be realised that for any two digit numbers, the maximum primitive multiplications you need to carry out is which is considerable amount of manual work for large values of . Can we do better than this?
Well, we actually can using the Karatsuba Integer Multiplication Algorithm.
Step 1 :- Write the numbers and which are to multiplied in the form :-
where is the number of digits in the number or . If is an odd number say , you can raise to the power as an optimal value, however any works just fine.
Step 3:- Recursively calculate and if the multiplicands are of a decent order say . You
might want to use the Grade school algorithm instead here if the order is less than that.
Step 4:- Recursively calculate (again if the order is decent enough) and then subtract and from it. This saves you from an extra work of calculating and seperately. Now do the remaining addition to get your product.
Now for our example, we consider the same multiplication prior stated i.e.:- of and .
Let , , and . here =
Step 1 :- = and =
Step 2 :- = . Subtract and =
Step 3 :- = =
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.