Multiplying Large Numbers with Karatsuba`s Algorithm
(Page 1 of 4 )
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.
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!
Next: Multiplication >>
More C++ Articles
More By Gabor Bernat
