Home arrow C++ arrow 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
(Page 1 of 4 )

If you take a walk in the park, a poet might say that you are evading the hectic schedule of your daily life in a dramatic environment. However, a physician or engineer would say that at 15:34 PM you started to move from coordinates X0, Y0 to X, Y at a rate of 1 meter per second, while you are burning 1000kJ, but mostly you are being slowed down by the wind blowing in front of you with 8 m/s.

You see, everything that happens around us can be reduced to numbers, which are the topic of this article. Mainly we will be discussing very large or very precise numbers.

For anyone who has just found this article, let me say it that this is the second part of a three part saga. All of them are published here on the Dev Shed Network, so if you missed the first one don't hesitate to make a search as we're going to pick up from where we left off in the last one; I won't cover the ground already crossed in the previous article. 

As you may know, in the first part we made the skeleton of the class within which we implement large numbers and also made sure that the time required for the reading procedure of the files or the algorithms themselves (the addition and subtraction) is as optimal as possible.

After completing the basic part, it's time to get into some more complex operations, specifically multiplication. We shall break the ice with the elementary school method, detailing its procedures and major disadvantages. After that I'll introduce you to the solution to our dilemma, namely Karatsuba's algorithm, and then explain the reasons why should we use it.

And since we don't like wasting time, in the end we will implement what we've learned in C++ using STL classes. So again I warn you to empower yourself with some knowledge in this domain to fully understand the code snippets that are going to be presented here. Here we go now... get ready!

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-2019 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials