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 -
  1. #include <iostream>  
  2. using namespace std;  
  3.   
  4. string add (string &s1, string &s2){  
  5. int carry=0,sum,i;  
  6.   
  7. string  min=s1,  
  8.  max=s2,  
  9.  result = "";  
  10.   
  11. // Finds the bigger string  
  12. if (s1.length()>s2.length()){  
  13.  max = s1;  
  14.  min = s2;  
  15. else {  
  16.  max = s2;  
  17.  min = s1;  
  18. }  
  19.   
  20. // Fills the result for overlapping regions of sum  
  21. for (i = min.length()-1; i>=0; i--){  
  22.  sum = min[i] + max[i + max.length() - min.length()] + carry - 2*'0';  
  23.   
  24.  carry = sum/10;  
  25.  sum %=10;  
  26.   
  27.  result = (char)(sum + '0') + result;  
  28. }  
  29.   
  30. // Summates the previous carry and the remaining digits of bigger string  
  31. i = max.length() - min.length()-1;  
  32.   
  33. while (i>=0){  
  34.  sum = max[i] + carry - '0';  
  35.  carry = sum/10;  
  36.  sum%=10;  
  37.   
  38.  result = (char)(sum + '0') + result;  
  39.  i--;  
  40. }  
  41.   
  42. // Adds the carry if remaining to the last digit e.g 999+1=1000  
  43. if (carry!=0){  
  44.  result = (char)(carry + '0') + result;  
  45. }  
  46.   
  47. return result;  
  48. }  
  49.   
  50. int main (){  
  51. // implementation  
  52. string a,b;  
  53. cin >> a >> b;  
  54. cout << add (a,b)<<endl;  
  55. return 0;  
  56. }  

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