IdeaMonk

thoughts, ideas, code and other things...

Thursday, October 30, 2008

Adding large numbers in C++

Just wrote a C++ snippet to add huge numbers using strings -
#include <iostream>
using namespace std;

string add (string &s1, string &s2){
int carry=0,sum,i;

string min=s1,
max=s2,
result = "";

// Finds the bigger string
if (s1.length()>s2.length()){
max = s1;
min = s2;
} else {
max = s2;
min = s1;
}

// Fills the result for overlapping regions of sum
for (i = min.length()-1; i>=0; i--){
sum = min[i] + max[i + max.length() - min.length()] + carry - 2*'0';

carry = sum/10;
sum %=10;

result = (char)(sum + '0') + result;
}

// Summates the previous carry and the remaining digits of bigger string
i = max.length() - min.length()-1;

while (i>=0){
sum = max[i] + carry - '0';
carry = sum/10;
sum%=10;

result = (char)(sum + '0') + result;
i--;
}

// Adds the carry if remaining to the last digit e.g 999+1=1000
if (carry!=0){
result = (char)(carry + '0') + result;
}

return result;
}

int main (){
// implementation
string a,b;
cin >> a >> b;
cout << add (a,b)<<endl;
return 0;
}

Output :

32485689234981709712094710984091842358764876328746187648716462938589273589723895789237587238947189748917894718973891728937189478913277893257891749817984719287439812789473289475328975981723894718927489127894712894

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

32485689234981709712094710984091842358764876328746187648716462938589273599723895789237587238947189748917894718973891728937189478913277893257891749817984719287439812789473289475328975981723894718927489127894712893

Labels: , ,

5 Comments:

At December 1, 2008 at 11:50 AM , Anonymous Anonymous said...

Thanks Dude ! Great Code

 
At December 23, 2010 at 5:37 AM , Anonymous ak said...

very good method ;)

 
At October 20, 2011 at 7:05 AM , Anonymous Anonymous said...

Can u explain why u have to add '0'?

 
At October 20, 2011 at 5:31 PM , Blogger Abhishek Mishra said...

To get the ascii equivalent of the numeric value. '0' is 48 in ascii and other digits are arranged sequentially, 0,1,2,3,4,5,6,7,8,9. So say you need to figure out ascii value for '5', we can quickly do '0'+5, and use that as a char value.

 
At November 27, 2011 at 1:17 AM , Blogger Abhay Bothra said...

Only replace
this:
sum = min[i] + max[i + max.length() - min.length()] + carry - 2*'0';
by:

sum = (min[i] - '0' ) + (max[i + max.length() - min.length()] - '0') + carry;

and a monkey could understand your code!
Brilliant!

 

Post a Comment

Subscribe to Post Comments [Atom]

<< Home