-1

The problem

I am trying to solve the following:

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?

Source

I keep getting false outputs because of precision errors. However, as you can see below, I try to make sure that nothing is rounded, or lost because of precision. The code I wrote falls short of the desired output (1366) by two (1364). How can optimize my code in order to not lose anything else because of precision and rounding errors?

My code

#include <iostream>
#include <tgmath.h>
#include <string>
using namespace std;

int main() {
    int sum=0;
    double N = pow(2.0, 1000.0);
    string num = to_string(N);
    for(int i=0; i<num.size(); i++) {
        sum += num[i] - '0';
    }
    cout<<sum;
    return 0;
}
Community
  • 1
  • 1
ripeat
  • 9
  • 5
  • Handle it the same way you would do it using pen and paper. Do addition with carries, do long multiplication, and so on. – David Schwartz Feb 26 '19 at 22:57
  • Don't use `double`, use more than one integer. As a simple first cut, use one integer for each digit of the number. Then do long addition (with carries), long multiplication, and so on. Or use a library that already does all this. – David Schwartz Feb 26 '19 at 22:57
  • 2
    Don't use numbers. Use text. That's what you use use when using pen and paper. Text is good at representing abstract concepts such as numbers. – Fureeish Feb 26 '19 at 22:58
  • What library do you suggest using @DavidSchwartz ? – ripeat Feb 26 '19 at 22:59
  • Strings work too. You'll have to write functions to do long addition and long multiplication on strings that represent integers in base 10. – David Schwartz Feb 26 '19 at 22:59
  • @ripeat OpenSSL has a bignum library, GMP (GNU multiprecision), or (likely best choice) [Boost.Multiprecision](https://www.boost.org/doc/libs/1_69_0/libs/multiprecision/doc/html/boost_multiprecision/intro.html). – David Schwartz Feb 26 '19 at 22:59
  • 1
    Look at the [answer](https://stackoverflow.com/a/45999579/4944425) by [Andre Kampling](https://stackoverflow.com/users/8051589/andre-kampling) in the duplicate Q&A, in particular his [working code](https://ideone.com/8HucrI) which is *similar* to yours. If you notice, the loop is limited to only the digits, because the string will end with something like `".0000"` and that char, `'.'`, would make the sum wrong. – Bob__ Feb 26 '19 at 23:28
  • The "already has an answer" post demo's gmpxx.h (integer) class named 'mpz_class'. – 2785528 Mar 02 '19 at 02:56

1 Answers1

1

According to WolframAlpha the result of 2^1000 is

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

That will never fit into an int or a double. You need to find a library that supports very large numbers. The GNU Multiple Precision Arithmetic Library is one such library.

Dustin Nieffenegger
  • 618
  • 7
  • 22
  • The limits of a 'double' in my environment are 1.79769e+308. Shouldn't 1.07151e+301 (2^1000) be stored in it? – ripeat Feb 26 '19 at 23:04
  • @ripeat -- *Shouldn't 1.07151e+301 (2^1000) be stored in it?* -- Not looking like like that. The answer shows you purely an integer. There is no floating point involved whatsoever. I believe this is where you started to go down the wrong track -- the answer requires *integer* or integer-like approaches ( approaches that mimic integer arithmetic), not floating point. – PaulMcKenzie Feb 26 '19 at 23:11