×

# 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
1 year, 10 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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

- 1 year, 10 months ago

Log in to reply

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.

- 1 year, 10 months 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$$.

Staff - 1 year, 10 months ago

Log in to reply

That's nice. What is the resultant complexity of the algorithm?

- 1 year, 10 months ago

Log in to reply

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.

- 1 year, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...