BigInteger addition

tux4life 0 Tallied Votes 268 Views Share

Hi there,

I've written a program which can add two numbers of unspecified length, isn't that nice?

To add two numbers you just do the following: addition(number1, number2); , where 'number1' and 'number2' are strings ...

E.g:

...
cout << addition("500","10") << endl; // Print '510' on the screen
...

P.S.: Sorry if my English is bad, my native language is Dutch ...

/******************************************************************************************************
* < BigInteger Addition > using strings;
*
* Written by Mathias Van Malderen;
* Copyright (c) 2009 Mathias Van Malderen;
*
* NOTE: -> It's NOT allowed to sell this source code to anyone !!!
*	-> You MAY use this code for any purpose, but on your own risk ...
*
*******************************************************************************************************/
#include <iostream>
#include <string>

using namespace std;

inline int ab(int a);
inline int min(int a, int b);
inline int max(int a, int b);
short str2digit(const string &str);
string digit2str(short digit);
void reverseStr(string &str);
void addZeros(string &str, int n);
string addition(string &s1, string &s2);
bool checkInt(const string &str);

int main()
{
	string num1, num2;
	
	cout << "Enter a very long number: ";
	cin >> num1;
	cout << "Enter another very long number: ";
	cin >> num2;
	cout << endl << endl;
	
	if(checkInt(num1) && checkInt(num2))
	{
		cout << "Sum = " << addition(num1, num2) << endl;
	} else {
		cout << "You have to enter two valid integers !" << endl;
	}
	
	return 0;
}

string addition(string &s1, string &s2)
{
	/* Calculate the sum of two (big) numbers (=integers) */
	if(s1.length() != s2.length())
	{
		int diff = ab(s1.length()-s2.length());
		if(max(s1.length(),s2.length()) == s1.length())
		{
			addZeros(s2,diff);
		} else {
			addZeros(s1,diff);
		}
	}
	
	string solution;
	string s_dig1;
	string s_dig2;
	int s = 0;
	bool carry = false;
	reverseStr(s1);
	reverseStr(s2);
	
	for(int i = 0; i < static_cast<int>(s1.length()); i++)
	{
		s_dig1 = s1[i];
		s_dig2 = s2[i];
		
		s = str2digit(s_dig1) + str2digit(s_dig2);
		
		if(carry)
		{
			s++;
			carry = false;
		}
		
		if(s > 9)
		{
			solution += digit2str(s-10);
			carry = true;
		} else {
			solution += digit2str(s);
		}
	}
	
	/* This code was added as a BUGFIX */
	/* Try to run this function without this bugfix with two arguments of length 1 and you'll get an incorrect result */
	/* For instance if you run this function (without this bugfix) with "5" and "9" as it's arguments, you'll get "4" as answer */
	
	/* BEGIN_OF_FIX */
	if(carry)
	{
		solution += "1";
	}
	/* END_OF_FIX */
	
	reverseStr(solution);
	return solution;
}

inline int ab(int a)
{
	/* Return the absolute value of an integer */
	return a>0?a:-a;
}

inline int max(int a, int b)
{
	/* Return the highest number of the two */
	return a>b?a:b;
}

inline int min(int a, int b)
{
	/* Return the lowest number of the two */
	return a<b?a:b;
}

void addZeros(string &str, int n)
{
	/* Add n zeros to the beginning of the string */
	string tmp;
	for(int i = 0; i < n; i++)
	{
		tmp = tmp + "0";
	}
	str = tmp + str;
}

short str2digit(const string &str)
{
	/* Convert a string to a digit */
	if(str.length() > 1) return -1;
	switch(str[0])
	{
		case '0':
			return 0;
		case '1':
			return 1;
		case '2':
			return 2;
		case '3':
			return 3;
		case '4':
			return 4;
		case '5':
			return 5;
		case '6':
			return 6;
		case '7':
			return 7;
		case '8':
			return 8;
		case '9':
			return 9;
		default:
			return -2;
	}
}

string digit2str(short digit)
{
	/* Convert a digit to a string */
	switch(digit)
	{
		case 0:
			return "0";
		case 1:
			return "1";
		case 2:
			return "2";
		case 3:
			return "3";
		case 4:
			return "4";
		case 5:
			return "5";
		case 6:
			return "6";
		case 7:
			return "7";
		case 8:
			return "8";
		case 9:
			return "9";
		default:
			return "";
	}
}

void reverseStr(string &str) 
{
    /* Reverse a string */
    int strlen;
    strlen = str.length();
    string revstr;

    if(strlen != 0)
    {
        for(int i=1; i<strlen+1; i++)
        {
		revstr = revstr + str[strlen-i];
        }
    }
	str = revstr;
}

bool checkInt(const string &str)
{
	/* Check whether the string contains a valid integer */
	string tmp_s;
	for(int i = 0; i < static_cast<int>(str.length()); i++)
	{
		tmp_s = str[i];
		if(str2digit(tmp_s) == -1 || str2digit(tmp_s) == -2)
		{
			return false;
		}
	}
	return true;
}
tux4life 2,072 Postaholic

Hello, I've rewritten 'str2digit' and 'digit2str':

short str2digit(const string &str)
{
	/* Convert a string to a digit */
	if(str.length() > 1) return -1;
		if(isdigit(str[0]))
			return (str[0] - '0');
	return -2;
}

string digit2str(short digit)
{
	/* Convert a digit to a string */
	string tmp;
	if(digit >= 0 && digit <= 9)
	{
		tmp = digit + '0';
		return tmp;
	}
	return "";
}
Nick Evan 4,005 Industrious Poster Team Colleague Featured Poster

You do realize that your str2digit function is actually a char2digit function right? I mean if you input a string "123", it'll return 1

tux4life 2,072 Postaholic

Yeah, but it doesn't make sense as I only want the first character to be converted, if the string (which has been passed as an argument has a length higher than 1, the function is returning an 'error code/value': -1) ...

Nick Evan 4,005 Industrious Poster Team Colleague Featured Poster

I meant to type -1, but forgot to press te '-' key.

But my point was: If the function only converts 1 char, why not make it's parameter a char instead of a std::string?
*mumbles something about efficiency*
Because when you do this: s_dig1 = s1[i] , you're actually converting a char to a string for your function. Why not skip this line and make your function accept chars instead of std::strings?

tux4life 2,072 Postaholic

I updated my str2digit function, it's also renamed to a more suitable name chr2digit:

short chr2digit(const char str)
{
	/* Convert a string to a digit */
	if(isdigit(str))
		return (str - '0');
}

I also had to make some other changes in my code to make it work fully ...
So, what do you think, do I have to repost the whole snippet again, but in it's updated form ?

Nick Evan 4,005 Industrious Poster Team Colleague Featured Poster

Don't know. You can't edit it any more?
You could always post it in a new snippet and ask for the deletion of this one I guess.


Also:

Your new function has a bug. Was happens if the char isn't a digit? You should specify a value to be returned. Your compiler should have given you a warning about this. Do you compile with -Wall ?

tux4life 2,072 Postaholic

Oh, I didn't notice it ...
I was just deleting and changing parts of the function, but I deleted the instruction return -1; by accident ...

Thank you for mentioning that !

BTW, I'm compiling this snippet with the Borland compiler (yeah I know it starts getting dated, but I just find it such a good compiler, and easy to use ... )
Sometimes I'm also using the MinGW compiler ...

Nick Evan 4,005 Industrious Poster Team Colleague Featured Poster

What I meant with -Wall was: all warnings on. GCC call this -Wall, Visual Studio calls it warning level 5. Don't know how it's called in Borland, but it's good practice to use a high warning-level

tux4life 2,072 Postaholic

Yes, but I already knew that the -Wall option activates all warnings ...
I looked it up and in Borland the option to set all warnings on is -w

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.