How Can I Implement Big Int Functionality in C++ for Project Euler Problems?

[trollcast]

Hi,

I'm working my way through the project euler problems in c++ and I've got to one where you have to sum 100 numbers that are each 50 digits long to find the first 10 digits of the sum.

Obviously I could solve it by summing each of the figits in turn then work with them to deal with carry overs.

However I was wondering if there was a way I could write some code to implement something like Java's Big Int datatype?

I'm a bit of a noob with c++ and my google fu isn't working tonight so any links or help would be great.

 

[jbunniii]

Certainly it's possible to write your own Big Integer class in C++. Here is library that someone else has already written, if you don't want to reinvent the wheel:

https://mattmccutchen.net/bigint/

 

[Adyssa]

There's an interesting solution to this problem. Given that you only require the first 10 digits of the sum, you can get away with only summing the first 11 digits of each number. Digits beyond the 11th will not affect the first 10 digits of the sum. With this in mind, you can solve the problem without using a Big Int implementation. I'll mention that I didn't realize this when I was attempting the problem, but read it in the forum after I had solved it.

Having said that, writing a Big Int library would be an interesting exercise. You need to perform addition, subtraction and other operations manually like you mentioned, one digit a time and carrying if necessary. Converting to a base higher than 10 is more efficient because you can represent numbers with less digits, and I think there are other tricks you can use too, perhaps someone can elaborate on exploiting binary operations and using bases that are powers of 2.

Here's some code that implements addition in base 10, untested but I think it works ok.

int add(num1, num2)
{
    int result = 0;
    int magnitude = 1;
    while (num1 > 0 && num2 > 0)
    {
        int digit1 = num1 % 10; // get the least significant digits of each number
        int digit2 = num2 % 10;
        result += (digit1 + digit2) * magnitude; // add the sum of these digits multiplied by their magnitude according to position in num1/num2 to our running total
        magnitude *= 10; // increment magnitude by power of 10
        num1 /= 10; // integer division drops the last digits
        num2 /= 10;
    }
    return result;
}

 

[trollcast]

Thanks guys,

jbunniii: I've already solved the problem using Python but I was more interested in how you could create a class to handle very large numbers.

Adyssa: Thanks for the example, I was thinking on something similar using C like strings to store the digits and then working with each element of the char array individually. There maybe some value to be gained out of maybe converting the decimal to maybe hexadecimal or even base 32 since these represent 4 and 5 binary bits respectively so it would be quite easy to implement binary additon and stuff for them.

 

[Snark1994]

I wouldn't use C strings - I would use the std::deque template (http://www.cplusplus.com/reference/deque/deque/), or maybe std::vector, depending on your exact implementation. Conversion to hexadecimal wouldn't make a lot of sense unless you were really worried about space, and trying to fit exactly 2 digits into each byte. In general, I would go for the simple implementation rather than an unnecessarily optimised one.

 

[d3mm]

Trollcast: C++ has two main "standard" libraries for general purpose programming, these being the standard library itself and the Boost library. Boost has a Bigint in Numerics. You might want to check out the source code.

Python really spoils you, it does so much out of the box and the standard library is amazing too.

Of course on this forum people probably use the domain-specific math and sci libs.

 

[chiro]

If you are using the code for non-commercial purposes I recommend this:

http://www.cs.sunysb.edu/~algorith/implement/shamus/implement.shtml

I have used it myself and it's very easy to get something up and running.

 

[d3mm]

There's an interesting solution to this problem. Given that you only require the first 10 digits of the sum, you can get away with only summing the first 11 digits of each number. Digits beyond the 11th will not affect the first 10 digits of the sum.

I just noticed that. Is there a 'proof' of that? It is hard to believe. What about the case of 1.9999999 etc?

 

[photo graphicus]

You may also have a look at InfInt's source code.

 

[phinds]

There's an interesting solution to this problem. Given that you only require the first 10 digits of the sum, you can get away with only summing the first 11 digits of each number. Digits beyond the 11th will not affect the first 10 digits of the sum.

Why would the 11th digit have any effect on the first 10 of the sum?