Home arrow C++ arrow Page 2 - Multiplying Large Numbers with Karatsuba`s Algorithm

Multiplying Large Numbers with Karatsuba`s Algorithm

Numbers are magic; magic by their properties, their existence, and most importantly, their huge impact on our day-to-day modern life. Everything can be reduced and narrowed down to numbers. In this second part of our series on large numbers, we'll delve more deeply into this magic.

Author Info:
By: Gabor Bernat
Rating: 5 stars5 stars5 stars5 stars5 stars / 12
July 22, 2008
  1. · Multiplying Large Numbers with Karatsuba`s Algorithm
  2. · Multiplication
  3. · Karatsuba's Algorithm
  4. · Apply What We Have Just Learned

print this article

Multiplying Large Numbers with Karatsuba`s Algorithm - Multiplication
(Page 2 of 4 )

Multiplication is different from the functions we've completed so far. There must be a reason why children remember mostly from their primary school learning one thing - and that's the multiplication. So the obvious question is, how much more complex is it?

The Romans themselves with their highly evolved society and the aqueducts had many problems with multiplication. The Romans' problem was that they did not use a radix (or base) number system. For instance, multiplication can be, of course, perceived and reduced to a repeated addition, but before you hop down to implement it in some pure code, think of the optimality of multiplying 9999 by 556445. For sure it would take a long time, which is unacceptable by any standards.

However, if we approach the problem again with the standard algorithm taught to us in the elementary school the situation already looks a lot better. All that we have to do is to start from the end of one of the elements and multiply with every digit the other number (note: to multiply this out to even 9 additions, for example, can take time).

At any rate, this is not too problematic. More than that, shifting each item with the position of the count it occupies from the back and adding all of the results, we end up with the final result.

An example:



1998 which can be perceived as 2997 + 19980 + 99900.



This results in a complexity of O(n2). It is not too bad; however, we can still improve on this. Don't throw away this method, however, as we shall come back to it. Nevertheless, the computation can take an awfully long time even with this method. Remember that addition had a complexity of O(n) and ran, for two 10 MB files, for 8.5 seconds. The difference may seem little, but imagine the difference for very, very large numbers.

For example, what about two 1MB numbers? These stand for 1024*1024 digits. Raise it to a power of two. That's 1024*1024*1024*1024, a significant difference at least. Anyway, some highly intelligent people looked over this method and found an even faster method. Shall we start learning it? Let's begin!

blog comments powered by Disqus

- Intel Threading Building Blocks
- Threading Building Blocks with C++
- Video Memory Programming in Text Mode
- More Tricks to Gain Speed in Programming Con...
- Easy and Efficient Programming for Contests
- Preparing For Programming Contests
- Programming Contests: Why Bother?
- Polymorphism in C++
- Overview of Virtual Functions
- Inheritance in C++
- Extending the Basic Streams in C++
- Using Stringstreams in C++
- Custom Stream Manipulation in C++
- General Stream Manipulation in C++
- Serialize Your Class into Streams in C++

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 

Developer Shed Affiliates


© 2003-2018 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials