Waste less time on Facebook — follow Brilliant.
×

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.

Note by Kunal Verma
5 months, 4 weeks ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Step 3:- Recursively calculate \(ac\) and \(bd\). It's always better.

This is wrong for two reasons. First, you will eventually need to compute single-digit by single-digit, which is not possible with Karatsuba's algorithm. (Remember that any recursion needs a base case.) Second, even if not, you will probably still want to use it for small enough \(a,b,c,d\), because Karatsuba's algorithm needs more additions than schoolbook method, and when \(a,b,c,d\) are small, additions and multiplications are roughly the same cost. Wikipedia says you want to use Karatsuba's algorithm only when the operands are at least 320 bits long, so when \(a,b,c,d\) are just, say, 10digits (\(10^{10} \approx 2^{33}\)), you will want to use schoolbook method. Ivan Koswara · 5 months, 3 weeks ago

Log in to reply

@Ivan Koswara Thanks. I'm still learning though and I wanted to just share a bit about it. That was a bit of my interpretation which obviously is wrong. I will do the needful changes. Kunal Verma · 5 months, 3 weeks ago

Log in to reply

This idea extends to matrix multiplication, where the result is more surprising. In particular, it shows that matrix multiplication need not be or order \( n^3 \). Calvin Lin Staff · 5 months, 3 weeks ago

Log in to reply

That's nice. What is the resultant complexity of the algorithm? Agnishom Chattopadhyay · 5 months, 4 weeks ago

Log in to reply

@Agnishom Chattopadhyay I'm new to algorithmic analysis so I might not be the best person to explain that. Hopefully you might find this useful Karatsuba Multiplication. Kunal Verma · 5 months, 3 weeks ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...