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

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 / 11
July 22, 2008
TABLE OF CONTENTS:
  1. · Multiplying Large Numbers with Karatsuba`s Algorithm
  2. · Multiplication
  3. · Karatsuba's Algorithm
  4. · Apply What We Have Just Learned

print this article
SEARCH DEVARTICLES

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.

blog comments powered by Disqus
C++ ARTICLES

- 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 
Support 

Developer Shed Affiliates

 




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