How can I represent the number 2 ^ 1000 in C ++?
So, I was trying to complete problem # 16 in Project Euler, http://projecteuler.net , if you haven't seen it. It looks like this:
2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^1000?
I am having a hard time figuring out how to represent the number 2 ^ 1000 in C ++. I guess there is a trick, but I am really stuck. I don't really want an answer to the problem, I just want to know how to represent this number as a variable, or maybe there is a trick, maybe someone can advise me?
source to share
Think of it as a string. This means that you need to write two pieces of code:
-
You need to write a piece of code to double a number, considering that number as a string.
-
You need to write a piece of code to sum the digits of a number represented as a string.
It's easy with these two parts.
source to share
One good algorithm to know about this issue:
2^1 = 2
2^2 = 2 x 2 = 2 + 2
2^3 = 2 x (2 x 2) = (2 + 2) + (2 + 2)
2^4 = 2 x [2 x ( 2 x 2)] = [(2 + 2) + (2 + 2)] + [(2 + 2) + (2 + 2)]
Thus, we have a definition recursive
for computing the cardinality of two in terms of an operation addition
:just add together two of the previous power of two.
This link deals with this problem very well.
source to share
The whole problem is coming up with a way to do it without actually calculating 2 ^ 1000.
However, if you want to compute 2 ^ 1000, which might be a good idea because it is a great way to check if your other algorithm is correct, you will need some kind of "bignum" library, for example gmp
:
mpz_t two_to_1000;
mpz_ui_pow_ui(two_to_1000, 2, 1000);
Or you can use the C ++ interface before gmp
. It doesn't do exponentiation, so the first part is a little more complicated, not less, but makes it easier to simplify the numbers:
mpz_class two_to_1000;
mpz_ui_pow_ui(two_to_1000.get_mpz_t(), 2, 1000);
mpz_class digitsum(0);
while (two_to_1000) {
digitsum += two_to_1000 % 10;
two_to_1000 /= 10;
}
(There's really no reason to do digitsum
a mpz
, so you might need to figure out how to prove that the result will fit in 32 bits, add that as a comment, and just use long
for digitsum
.)
All that said, I probably wouldn't write this code gmp
to test it when it's all a one-liner in Python:
print(sum(map(int, str(2**1000))))
And even if converting bignum to string to convert each digit to int in order to sum them is perhaps the least efficient way to solve it, it still takes less than 200 units on the slowest machine I'm here. And there is no reason why the double check should be in the same language as the actual solution.
source to share
Here is the complete program. The numbers are held in the vector.
#include <iostream>
#include <numeric>
#include <ostream>
#include <vector>
int main()
{
std::vector<unsigned int> digits;
digits.push_back(1); // 2 ** 0 = 1
const int limit = 1000;
for (int i = 0; i != limit; ++i)
{
// Invariant: digits holds the individual digits of the number 2 ** i
unsigned int carry = 0;
for (auto iter = digits.begin(); iter != digits.end(); ++iter)
{
unsigned int d = *iter;
d = 2 * d + carry;
carry = d / 10;
d = d % 10;
*iter = d;
}
if (carry != 0)
{
digits.push_back(carry);
}
}
unsigned int sum = std::accumulate(digits.cbegin(), digits.cend(), 0U);
std::cout << sum << std::endl;
return 0;
}
source to share
You will need a 1000 bit integer to represent 2 ^ 1000; I've never heard of a car like this. But there are many large integer packages that do arithmetic versus the number of machine words that are needed. The simplest solution might be to use one of them. (Although, given the specific operations you need, doing arithmetic on a string, as suggested by David Schwartz, might be appropriate. It's generally not a good idea, but since everything you do is multiply by two and then take decimal numbers, it might turn out well.)
source to share