Karatsuba Integer Multiplication Algorithm

The Karatsuba Integer Multiplication Algorithm is a really simple,fast recurrence based method to multiply two n 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 4 digit numbers, say 9999 9999 and
9998 9998 . It can be seen that to find a product and of these two numbers, we have two perform 2× 42 = 32 2 \times \ 4^{2} \ = \ 32 primitive multiplications accompanied with some primitive additions. It can now be realised that for any two n n digit numbers, the maximum primitive multiplications you need to carry out is 2n22n^{2} which is considerable amount of manual work for large values of n 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 X and Y Y which are to multiplied in the form :-

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

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

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

Step 3:- Recursively calculate ac ac and bd bd if the multiplicands are of a decent order say 10510^{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)× (c + d) ( a \ + \ b) \times \ ( c \ + \ d) (again if the order is decent enough) and then subtract adad and bdbd from it. This saves you from an extra work of calculating ad ad and bc 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 9999 and 9998 9998 .

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

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

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

Step 3 :- 9999× 9998 9999 \times \ 9998 = 104× 9801 + 102× 19503 + 9702 10^{4} \times \ 9801 \ + \ 10^{2} \times \ 19503 \ + \ 9702 = 99970002 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
3 years, 5 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Step 3:- Recursively calculate acac and bdbd. 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,da,b,c,d, because Karatsuba's algorithm needs more additions than schoolbook method, and when a,b,c,da,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,da,b,c,d are just, say, 10digits (101023310^{10} \approx 2^{33}), you will want to use schoolbook method.

Ivan Koswara - 3 years, 5 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.

Kunal Verma - 3 years, 5 months ago

Log in to reply

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

Agnishom Chattopadhyay Staff - 3 years, 5 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.

Kunal Verma - 3 years, 5 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 n3 n^3 .

Calvin Lin Staff - 3 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...