# 2^1000 result too large!

• 09-28-2008
pobri19
2^1000 result too large!
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&#37; 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 :)
• 09-28-2008
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:

Code:

```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
• 09-28-2008
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.
• 09-28-2008
anon
The class declaration looks like this:
Code:

```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.
• 09-28-2008
pobri19
Man, you're a genius ;) Thanks!
• 09-28-2008
CornedBee
The best big number class is GMP.
• 09-28-2008
is this a project Euler problem? seems like it would be
• 09-29-2008
samGwilliam
Quote:

Originally Posted by 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:

Code:

```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?
• 09-29-2008
matsp
Quote:

Originally Posted by samGwilliam
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
• 09-29-2008
grumpy
Quote:

Originally Posted by anon
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.
• 09-29-2008
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....
• 09-29-2008
laserlight
Quote:

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.