Project Euler #16: Answer 2 digits off

Question

The answer I get is 1364, but the correct answer is 1366. Am I getting the wrong answer because I convert double digits = pow(2,1000) to string dig = std::to_string(digits), or is there something else I'm missing?

#include <iostream>
using std::endl; using std::cout;
#include <string>
using std::string;
#include <cmath>

int computeSum(string);

int main(void){

    double digits = pow(2,1000);

    string dig = std::to_string(digits);

    cout << computeSum(dig) << endl;

    return 0;

}

int computeSum(string dig){

    int sum(0);

    for(char n : dig)
        sum+=(n-48); // or (n-'0')  

    return sum;

}

EDIT:

Solution: I needed to add the if (n!='.') condition as (n-48) converts the . to its ASCII value of 46, giving me a -2.

for(char n : dig){
    if(n!='.')
        sum+=(n-48); // or (n-'0')  
}

I used *BC math* in PHP in order to solve the problem. After googling for a C++ alternative I found [the following repository](https://github.com/DesarrollosCuado/BCMath-for-Cpp). — HamZa, May 26 '15 at 19:24
This is why some of these questions are biased, depending on the language used. This is trivial using `Java` and the `BigInteger` class. C++ doesn't have such built-in functionality, unless you use a third-party library. — PaulMcKenzie, May 26 '15 at 19:26
I found the problem. When you compute 2 ^ 1000 and store it in `digits`. The result will have a dot (obvious!). When you convert it to string, it will still contain this dot. Now a dot is 46, remove 48 you get -2. So when you iterate through your string, it will stumble upon the dot and add -2. There's your 2 digits off problem. You could add an if statement in the for loop to return the sum when it encounters a dot character. — HamZa, May 26 '15 at 19:32
HamZa, you genius. That worked. I added an `if (n!='.')` and the answer is now correct. — Ishaan, May 26 '15 at 19:40
@ishyfishy I now start wondering whether what you get is portable or is implementation defined. It seems extremely fishy, and I won't bet on it. It's probably ok in this case as you're using a power of 2. — vsoftco, May 26 '15 at 19:45

vsoftco · Answer 1 · 2015-05-26T19:58:10.267

Your answer is off because in the line

double digits = pow(2, 1000);

you store the result as a double, however the double loses precision when representing integers this large, as it uses a floating point representation.

You should use an integer and probably compute the sum of the digits iteratively in a multiplication loop, at each iteration reducing the result. Otherwise, you need to use a big int library, such as Boost.Multiprecision. Quick example of the latter:

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>

int main()
{
    using namespace boost::multiprecision;

    // Repeat at arbitrary precision:
    cpp_int u = 2;
    cpp_int result = pow(u, 1000);

    int sum = 0;
    for (auto elem : result.str()) // use the string representation
        sum += elem-'0';

    std::cout << result.str() << std::endl; // prints 2^1000
    std::cout << sum << std::endl; // prints the sum of the digits
}

EDIT

I realized that in this case @HamZa's comment below your answer is correct. A power of 2 in the range of a double is faithfully represented by a floating point representation, so you don't lose any precision in this case. The issue is indeed the .0000 that appears in the string representation. However, if you use 3 as a base, then all bets are off, and you cannot simply use std::pow.

Please see: http://stackoverflow.com/a/7372091/4907651. Is that answer incorrect? — Ishaan, May 26 '15 at 19:17
@ishyfishy sorry, I just edited it. I first thought you use an `int`. See also the last part of the answer you just linked. — vsoftco, May 26 '15 at 19:19
Double losing precision was the last thing that came to my mind as the answer was only 2 digits off. Thanks, I will try the method you suggested and see if that works. — Ishaan, May 26 '15 at 19:26

score 0 · Answer 2 · answered May 26 '15 at 19:24

0

You can also use this method of conversion

#include <iostream>
# include <cmath>
# include <string>
using namespace std;

int main() {
    cout<<std::to_string(pow((double)2,1000));
    return 0;
}

http://ideone.com/MZp1tN

answered May 26 '15 at 19:24

That's really weird. If I initialize my string with the output of that program on Ideone, the answer is 1366. Yet if I make my string equal to `std::to_string(pow((double)2,1000))`, I get 1364. – Ishaan May 26 '15 at 19:35

Project Euler #16: Answer 2 digits off

2 Answers2