2^1000 result too large!

[pobri19]

So I've got a challenge to get the result of 2^1000, then add each digit of that result together. The only problem is, the maximum size integer you can use in C++ is a 64 bit integer, which can store a maximum value of 2^64. So, to be honest, I have NO idea how this is going to be possible (But there HAS to be a way, 100% guaranteed)... I'd like some hints towards a solution if possible (that is if anyone knows ;o). So yeah, some hints would be nice! Thanks

P.s I'm sure a few of you know where this challenge is coming from

[anon]

Unless there is some mathematical answer you might use (or write your own minimal) large number class. For example I wrote my own small Large class for this and the following user program:

int main()
{
    Large num("1");
    for (int i = 0; i != 1000; ++i) {
        num.multiply_by_two();
    }
    std::cout << num << '\n' << num.sum_digits() << '\n';
}

And got the result (hope it is correct, seemed to work ok for smaller numbers):

10715086071862673209484250490600018105614048117055 33607443750388370351051124936122493198378815695858 12759467291755314682518714528569231404359845775746 98574803934567774824230985421074605062371141877954 18215304647498358194126739876755916554394607706291 45711964776865421676604298316526243868372056680693 76
1366

[pobri19]

Wow. Cheers for that man! That's the right answer Very nice. Oh but how did you make the class haha, did you do it in chunks and store the result in a string? I don't really know how it works, but I thought it would be harder than that.

[anon]

The class declaration looks like this:

class Large
{
    std::vector<char> buffer;
public:
    Large(const std::string& s_num);
    void multiply_by_two();
    unsigned sum_digits() const;
    friend std::ostream& operator<<( std::ostream& os, const Large& num);
};

So each digit is represented as a char (well, actually a char in range 0 - 9, and the constructor and the output routine take care of adding/substracting '0'. I also stored the digits in reverse order internally to make multiplying easier but this is just an implementation detail).

The only hard thing is to multiply by two. But you do know how to do this on paper? (multiply each digit by 2 and carry over 1 if the result is more than 9.

[pobri19]

Man, you're a genius Thanks!

[CornedBee]

The best big number class is GMP.

[nadroj]

is this a project Euler problem? seems like it would be

[samGwilliam]

Unless there is some mathematical answer you might use (or write your own minimal) large number class. For example I wrote my own small Large class for this and the following user program:

int main()
{
    Large num("1");
    for (int i = 0; i != 1000; ++i) {
        num.multiply_by_two();
    }
    std::cout << num << '\n' << num.sum_digits() << '\n';
}

And got the result (hope it is correct, seemed to work ok for smaller numbers):

10715086071862673209484250490600018105614048117055 33607443750388370351051124936122493198378815695858 12759467291755314682518714528569231404359845775746 98574803934567774824230985421074605062371141877954 18215304647498358194126739876755916554394607706291 45711964776865421676604298316526243868372056680693 76
1366

That's pretty cool.

Did you store the number as a byte per digit and perform the carrying manually or something?

[matsp]

That's pretty cool.

Did you store the number as a byte per digit and perform the carrying manually or something?

I think that's implied in the answer anon gave.

--
Mats

[grumpy]

Unless there is some mathematical answer you might use (or write your own minimal) large number class.

There are mathematical results that make it possible to get an answer without computing the actual value of 2^1000. Have a look here.

[arpsmack]

Just so you're aware, DigitSum arithmetic as described on that page is vastly different from calculating the sum of the digits of 2^1000. For starters, the DigitSum of any number results in a single digit answer. That should have been a huge clue right there....

[laserlight]

There are mathematical results that make it possible to get an answer without computing the actual value of 2^1000.

Unfortunately, the challenge requires one to compute 2^1000, and only then sum its digits.