Storing and using large integers.

[RAWBERRY]

I am currently doing some of the problems on projecteuler.net. Right now I am on problem 13 and having difficulty using the 50 digit numbers which I am required to add together. I feel like people commonly run into the issue of using integers which are larger than 64-bits, yet I am having difficulties finding a clean solution. Any help on this would be greatly appreciated! Thanks.

[Disch]

Get a bignum lib.

http://gmplib.org/

[Albatross]

+1 Disch.

However, if you don't want to use a bignum library for whatever reason (i.e. you want all your code to be your own), then I might recommend using an std::vector of digits inside a class that has the + operator overloaded.

Good luck!

-Albatross

[RAWBERRY]

I would really like to stay away from external libraries if possible. However, I did see someone else mention designing my own class to store the data I need. Albatross, if you could elaborate on your suggestion, I would really appreciate it. I have a limited understanding of classes and what I can actually do with them. Hopefully it's not too far over my head!

[D80DSL3A]

There was a contest a few months ago in the lounge to design a bignum class.
http://www.cplusplus.com/forum/lounge/32041/
You may get some good ideas there. Everyone's entries were class based so you could maybe learn a lot from them.

I took a crack at writing a program to make adding two big numbers as simple as possible. It handles only this task but should work for arbitrarily long integers.
Hopefully you are familiar with the string class. Perhaps someone could suggest a way to simplify my approach here. I provide some explanations in the code comments:

#include<iostream>
#include<string>
using namespace std;

int main(void)
{
	// the two "numbers" to be added. Make them as long as you like.
	string numStr1 = "662357";
	string numStr2 =  "56487";// sum should = 718844

	// keeping track of which string is longest using references
	string& rLongStr = numStr1.length() > numStr2.length() ? numStr1 : numStr2;
	string& rShortStr = numStr1.length() <= numStr2.length() ? numStr1 : numStr2;

	// initialize the sum with the long string but with space for a final carry at the beginning
	string numStrSum = '0' + rLongStr;// the '0' in case of a final carry

	// must go through the strings backwards since the least
	// significant digit is at the end, not the beginning.
	string::reverse_iterator r_itShort, r_itSum;
	r_itShort = rShortStr.rbegin();// point to last "digit" in the short string
	r_itSum = numStrSum.rbegin();// same for sum string

	// add the "digits" one by one from end to beginning of the short string
	while( r_itShort != rShortStr.rend() )
	{
		*r_itSum += *r_itShort - '0';// "add" the digits
		if( *r_itSum > '9' )// must carry a one to the next "digit"
		{
			*(r_itSum + 1) += 1;
			*r_itSum -= 10;
		}
		++r_itShort;// move back 1 character
		++r_itSum;// in each string
	}
	if( numStrSum.at(0) == '0' )// if 1st character is stiil '0'
		numStrSum.erase(0,1);// erase it

	// output result
	cout << numStrSum;// get "718844" for the case above
	
	cout << endl;
	return 0;	
}

[RAWBERRY]

Very helpful post. I honestly didn't realize how complex making a class for bignums would be. Should be fun! Looking forward to diving deeper into classes and what exactly I can do with them. Thank you!

[RAWBERRY]

I was looking over fun2code's implementation of bignum addition and I had a question.

Why are you using pointers here?

// add the "digits" one by one from end to beginning of the short string
	while( r_itShort != rShortStr.rend() )
	{
		*r_itSum += *r_itShort - '0';// "add" the digits
		if( *r_itSum > '9' )// must carry a one to the next "digit"
		{
			*(r_itSum + 1) += 1;
			*r_itSum -= 10;
		}
		++r_itShort;// move back 1 character
		++r_itSum;// in each string
	}
	if( numStrSum.at(0) == '0' )// if 1st character is stiil '0'
		numStrSum.erase(0,1);// erase it 

I've come to understand everything else, but I'm just a little confused as to why you have to use pointers there. And what is the point of subtracting the '0'?

EDIT: Derp! The r_itSum and r_itSmall are pointing to rShortStr and numStrSum. I feel like I understand this pretty well now, thanks! I'll post my implementation when I finish.

[Browni3141]

Using a bignum for projecteuler is overkill. Almost all of the problems are doable with 64-bit integers. Most of the one's that can't can be done with arrays/vectors and the arithmetic algorithms you learned in elementary school. I can think of one off the top of my head where you really do need to write/download a full bignum.
http://projecteuler.net/index.php?section=problems&id=80

Edit: You should probably get a bignum. Even if you don't need one now you might have need of one later.

[D80DSL3A]

@RAWBERRY:
Re:

The r_itSum and r_itSmall are pointing to rShortStr and numStrSum.

Those are actually iterators, which are similar to pointers. The ones in use are "reverse" iterators. They move through the strings backwards.

Re:

And what is the point of subtracting the '0'?

I'm manipulating character values here not integer values. The character '0' has an ascii value = 48 not 0. Suppose I want to get '3' + '2' = '5'. Adding the ascii values wouldn't work right.
I would get '3' + '2' = 51 + 50 = 101 = acii value of 'e'.
I'm subtracting '0' to get an offset to the character sought:
'3' + ( '2' - '0' ) = 51 + ( 50 - 48 ) = 51 + 2 = 53 = ascii value of '5'
Does that make sense?

NOTE: The program I gave is ready for use. Just change the values for numStr1 and numStr2 to what you want (eg. some 50 digit #'s). Better yet, modify the program so that it reads in strings input by the user for numStr1 and numStr2. This way the program doesn't have to be rebuilt every time you change the values.
ie. Replace:

string numStr1 = "662357";
string numStr2 =  "56487";// sum should = 718844 

With:

string numStr1;
string numStr2;
cout << "Enter 1st number: "; cin >> numStr1;
cout << "Enter 2nd number: "; cin >> numStr2;

Also:

Browni3141 wrote:

Using a bignum for projecteuler is overkill. Almost all of the problems are doable with 64-bit integers. Most of the one's that can't can be done with arrays/vectors and the arithmetic algorithms you learned in elementary school.

True. Use of a full on general purpose bignum library may be overkill. My method above just implements the grade school method for adding two numbers on paper.
Did you get problem #16? (find the sum of the digits of 2^1000)
http://projecteuler.net/index.php?section=problems&id=16
I recall you discussing that one previously. Did you solve it using 64-bit integers?

[Browni3141]

Yes, I solved that one. I just looked at my code and it was absolutely horrendous. I just improved it and can now get the answer for 2^100000 in about 2 seconds. I'm using a vector of 64-bit integers.

Edit: I'm kind of addicted to Project Euler. I like solving problems like this. If you can think of any problems I'd be glad to here them. ;)

[RAWBERRY]

So I took it upon myself to finally attempt and piece this all together. I feel I am very close, but something isn't quite right.

First, here's my implementation of the bignum addition into a class.

#include<iostream>
#include<string>
using namespace std;

string temp_sum = "0";

class bignum
{
    public:
    string c_bignumStr1;
    string c_bignumStr2;
    string c_bignumSum;

    void bignumAdd(string bignumStr1, string bignumStr2)
    {
        //Definition and declaration of our two bignums
        c_bignumStr1 = bignumStr1;
        c_bignumStr2 = bignumStr2;

        //Keep track of which bignum is larger using references (&)
        string &rLargeBignum = bignumStr1.length() > bignumStr2.length() ? bignumStr1 : bignumStr2;
        string &rSmallBignum = bignumStr1.length() <= bignumStr2.length() ? bignumStr1 : bignumStr2;

        //Define our bignum summation
        string bignumSum = '0' + rLargeBignum;

        //Addition, elementary style! We go through each digit, from last to first.
        string::reverse_iterator rit_SmallBignum, rit_bignumSum; //Reverses the order of each string
        rit_SmallBignum = rSmallBignum.rbegin();
        rit_bignumSum = bignumSum.rbegin();

        //Here we add each didgit of our bignum together
        while (rit_SmallBignum != rSmallBignum.rend())
        {
            *rit_bignumSum += *rit_SmallBignum - '0';
            if (*rit_bignumSum > '9') //This if statement carries the 1 if our single digits add up to be a double-digit.
            {
                *(rit_bignumSum + 1) += 1;
                *rit_bignumSum -= 10;
            }
            ++rit_bignumSum;
            ++rit_SmallBignum;
        }
        if( bignumSum.at(0) == '0' )
            bignumSum.erase(0,1);

            c_bignumSum = bignumSum;
            temp_sum = bignumSum;
    }

    void printSum()
    {
        cout << c_bignumSum;
    }

};

A quick test of this code adding two 50-digit numbers (37107287533902102798797998220837590246510135740250, 46376937677490009712648124896970078050417018260538) with wolframalpha.com for proof checking confirms it is working.

However, when I attempt to implement it inside a for loop, I get some strange output

int main()
{
    //The intimidating list of bignums which will be added together.
    string list[100] = {
(the 100 50-digit numbers were removed due to post length)
};

    bignum largeaddition;


    for (int count = 0; count < 99; count++)
    {
        largeaddition.bignumAdd(temp_sum, list[count]);
    }
    largeaddition.printSum();
    return 0;
}

And gives me the output:

f83872696164404113051174692757394181992395501560982
Process returned 0 (0x0)   execution time : 0.427 s
Press any key to continue.

Much thanks for all the help everyone. I'm really learning a lot!

[buffbill]

...or perhaps this:

int main()
{int n=0,m=0;
char s1[81];
char s[81];
    cout<<"\nadding large numbers";
    cout<<"\nenter a number \n";
    n=atoi(gets(s));
    cout<<"\nenter a second number \n";
    m=atoi(gets(s1));
    cout<<"addition gives "<<m+n<<endl;
    
cout<<"\npress any key...";
cin.get();
return 0;
}   

[RAWBERRY]

I don't want the program to take in any input. I have the values I want added together within the code already, I just can't figure out why my answer is coming out the way it is.

[D80DSL3A]

@RAWBERRY
It looks like the method I posted was incomplete. The while loop adds the digits in the short string to the longer one but there's nothing to continue carries in the long string after that.
This case fails: 95 + 6 = :1 instead of 101 because no carry is done for the lead digit in the sum.

Adding a second while loop after the first one to continue the carry operation appears to work.
Try adding this after line 43 in your code posted above:

while( rit_bignumSum != bignumSum.rend() )
{
	if( *rit_bignumSum > '9' )
	{
		*(rit_bignumSum + 1) += 1;
		*rit_bignumSum -= 10;
	}
	++rit_bignumSum;
}

Sorry about the missed detail!