Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Writing a Big Int in C++

  1. Feb 28, 2013 #1

    trollcast

    User Avatar
    Gold Member

    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.
     
  2. jcsd
  3. Feb 28, 2013 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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/
     
  4. Mar 1, 2013 #3
    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.

    Code (Text):
    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;
    }
     
  5. Mar 1, 2013 #4

    trollcast

    User Avatar
    Gold Member

    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.
     
  6. Mar 3, 2013 #5
    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.
     
  7. Mar 19, 2013 #6
    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.
     
  8. Mar 19, 2013 #7

    chiro

    User Avatar
    Science Advisor

  9. Mar 20, 2013 #8
    I just noticed that. Is there a 'proof' of that? It is hard to believe. What about the case of 1.9999999 etc?
     
  10. Jul 2, 2015 #9
    You may also have a look at InfInt's source code.
     
  11. Jul 2, 2015 #10

    phinds

    User Avatar
    Gold Member
    2016 Award

    Why would the 11th digit have any effect on the first 10 of the sum?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Writing a Big Int in C++
  1. Writing a program in C (Replies: 8)

Loading...