Multiplying Large Numbers with Karatsuba`s Algorithm - Apply What We Have Just Learned
(Page 4 of 4 )
As we passed through the previous pages we learned all that we are going to need in order to produce the desired result. Because we have real numbers and not only integers we'll resolve this problem by calling Karatsuba's algorithm for the two numbers and calculate the place of the comma in the result after finishing the operation. We simply have to add the real length of the two numbers. This is realized by the following line.
And here let me present Karatsuba's method:
Large_Numbers
Large_Numbers::Karatsuba (Large_Numbers& ls, Large_Numbers& rs)
{
Large_Numbers result; // Here we'll store the result
if (ls.all < SWITCH_TO_CLASSIC && rs.all < SWITCH_TO_CLASSIC)
{
ClassicMultiply (result, ls, rs);
}
else
{
unsigned long int size = std::max (ls.all, rs.all) / 2;
string::iterator ls_end = ls.number.end (); string::iterator rs_end = rs.number.end ();
string::iterator ls_begin = ls.number.begin ();
string::iterator rs_begin = rs.number.begin ();
long int leftLeftLength = ls.all - size;
if (leftLeftLength < 0) leftLeftLength = 0;
long int rightLeftLength = rs.all -size;
if (rightLeftLength < 0) rightLeftLength = 0;
string::iterator ls_middle = ls_begin + leftLeftLength;
string::iterator rs_middle = rs_begin + rightLeftLength;
Large_Numbers x1;
if (leftLeftLength)
x1.Set (string (ls_begin, ls_middle),
std::distance (ls_begin, ls_middle));
Large_Numbers x2;
x2.Set (string (ls_middle, ls_end),
std::distance (ls_middle, ls_end));
Large_Numbers y1;
if (rightLeftLength)
y1.Set (string (rs_begin, rs_middle),
std::distance (rs_begin, rs_middle));
Large_Numbers y2;
y2.Set (string (rs_middle, rs_end),
std::distance (rs_middle, rs_end));
Large_Numbers sumX = x1 + x2;
Large_Numbers sumY = y1 + y2;
Large_Numbers X = Karatsuba(x1, y1)
Large_Numbers Y = Karatsuba(x2, y2);
Large_Numbers Z = Karatsuba (sumX, sumY) - X - Y;
X.ShiftIt (2*size);
Z.ShiftIt (size);
result = X + Y + Z;
}
return result;
}
Brief explanation: If we're in the range simply calculate the result with the Classic method. Otherwise, find the middle, divide the numbers, calculate the sum of the elements, call Karatsuba's algorithm to calculate the multiplications, shift the items, and add the items. Return the result.
Now all we need to do is check out the results! For some obvious reasons now I won't venture to multiply two numbers that are 10 MB because it would take an awfully long time on my decent system (AMD Sempron 3000+ with default clocks and 1 GB DDR400 memory with a Western Digital 200 GB ATA133 Hard Disk). But look first for two 10K numbers and after it two 100K numbers.
And a little longer for the 100K numbers:
As you can see multiplication is a bit more complex than addition and takes much more time to complete. Also here is as promised the source code with the class implementation, so you can skim through it freely and see how it works with a debugger eventually. The project that is included is created with Visual Studio 2005 so with earlier versions you can't open it, but if you create a new solution it should work.
I hope you have enjoyed this session too. I wish you a nice day and all the best until the upcoming next part in which we'll try to solve the divide operation. If you have some additional question related to this part or even the previous one or observations about it, you shouldn't hesitate to visit our friendly ever-growing forum at the Dev Hardware.
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
