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:
999*123
2997
1998 which can be perceived as 2997 + 19980 + 99900.
999
122877
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!
Next: Karatsuba's Algorithm >>
More C++ Articles
More By Gabor Bernat
