sum of digits of large numbers (10^9)?

Question

I am trying to solve this particular problem: Project Euler #16:

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?

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

int main()
{
   int num;
   cin >> num;
   long double n = pow(2, num);
   cout << fixed << n << endl;
   int sum = 0;
   while(n != 0.0)
   {
      sum = sum + fmod(n, 10);
      n = floor(n/10);
   }
   cout << sum << endl;
}

The output when user input is 1000 is:

1181

However, the internet mentions the correct answer to be 1366 instead of the 1181 I got.

Answer 1

The problem is not about the first calculation:

long double n = pow(2, num);

as even the regular double type (max: 1.79769e+308) will hold 2^1000 = 1.07151e+301 without any problems especially that this is a base 2 calculation.

Note that your using the double versions pow(), fmod() and floor() instead of the long double versions powl(), fmodl() and floorl(). But that is as I said not the problem and won't change anything.

But the calculation in the while loop will lack in precision and rounding errors. Further never check floating point numbers for (un)equality when doing arithmetics with them, see here on SO (there are a lot of other discussion and threads in the web about that topic).

In short:
I assume that your fmod() and floor() will lead to precision loss and rounding errors.

---

Here is a working solution (see at ideone) for your case converting the double to a std::string and iterating through every character of the string adding that char converted to an integer.

In short:
It is just using the initial calculation (just with double) and convert that to a string.

#include <iostream>
#include <cmath>

int main ()
{
   int num;
   std::cin >> num;
   double n = pow(2, num); /* note I use just double */

   std::string nstr = std::to_string(n);
   const char* nstr_p = nstr.c_str();

   std::cout << std::fixed << nstr << std::endl;
   int sum = 0;
   while (std::isdigit(*nstr_p)) /* number contains dot and fractional (.0000) */
   {
      sum = sum + (*nstr_p - '0'); /* convert character to integer and sum it */
      nstr_p++;
   }
   std::cout << sum << std::endl;
}

Output:

1366

Note that the conversion: (*nstr_p - '0') assumes an encoding like ASCII or others where numbers are incrementing without gaps in their hexadecimal representation.

Answer 2

Here is a C++ approach using the multi-precision integer arithmetic of GMP (note gmpxx.h).

I prefer integers when possible, and gmp makes working with big integers easy enough.

Like Andre, I created a std::string of the result, and added the digits.

---

Environment:

Ubuntu 15.10, 64 bit, using g++-5 is v5.2.1, on older Dell

---

Code:

#include <chrono>
// 'compressed' chrono access --------------vvvvvvv
typedef std::chrono::high_resolution_clock  HRClk_t; // std-chrono-hi-res-clk
typedef HRClk_t::time_point                 Time_t;  // ...-time-point
typedef std::chrono::milliseconds           MS_t;    // std-chrono-milliseconds
typedef std::chrono::microseconds           US_t;    // std-chrono-microseconds
typedef std::chrono::nanoseconds            NS_t;    // std-chrono-nanoseconds
using   namespace std::chrono_literals; // support suffixes like 100ms, 2s, 30us
#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <cassert>

#include <gmpxx.h>  // multiprecision arithmetic:
                    // no rounding errors because mpz_class is integer

class T526_t
{
public:
   T526_t() = default;
   ~T526_t() = default;

   int exec()
      {
         Time_t start_us = HRClk_t::now();

         mpz_class  N("1"); // initialize multi-precision integer to value 1

         std::string s;
         int i;
         for (i=0; true; ++i) // run forever
         {
            std::stringstream ss;
            ss << N;              // stream i/o from gmpxx.h
            N = N * 2;            // compute next value

            if(i <= 16) // confirm the first 17 values
            {
               std::cout << "\n"
                         << "  2 ^" << std::setw(3) << i
                         << "  size:" << std::setw(2) << ss.str().size()
                         << "  " << digiComma(ss.str())
                         << "  sum : " << sumOfDigits(ss.str());
            }
            s = ss.str();

            if (1000 == i) break; // enough already
         }

         std::cout << "\n\n"
                   << "  2 ^" << std::setw(5) << i
                   << "  size:" << std::setw(4) << s.size()
                   << "  \n\n" << digiComma(s)
                   << "\n\n  sum-of-digits: " << sumOfDigits(s) << std::endl;

         auto duration_us =
            std::chrono::duration_cast<US_t>(HRClk_t::now() - start_us);

         std::cout << "\n\n  duration: "
                   << digiComma(std::to_string(duration_us.count()))
                   << " us" << std::endl;

         return (0);
      }


private: // methods

   size_t sumOfDigits(std::string s)
      {
         size_t retVal = 0;
         for (uint i=0; i<s.size(); ++i)
         {
            retVal += s[i] - '0';
         }
         return retVal;
      }

   std::string digiComma(std::string s)
      {  //vvvvv--sSize must be signed int of sufficient size
         int32_t sSize = static_cast<int32_t>(s.size());
         if (sSize > 3)
            for (int32_t indx = (sSize - 3); indx > 0; indx -= 3)
               s.insert(static_cast<size_t>(indx), 1, ',');
         return(s);
      }


}; // class T526_t


int main(int , char** )
{
   Time_t start_us = HRClk_t::now();

   int retVal = -1;
   {
      T526_t   t526;
      retVal = t526.exec();
   }

   auto  duration_us =
      std::chrono::duration_cast<US_t>(HRClk_t::now() - start_us);

   std::cout << "\n  FINI   " << duration_us.count() << " us" << std::endl;
   return(retVal);
}

---

Results:

Rule-526: dumy526.cc
rm -f dumy526
g++-5 -m64  -O0 -ggdb -std=c++14 -Wall -Wextra -Wshadow -Wnon-virtual-dtor
                -pedantic -Wcast-align -Wcast-qual -Wconversion -Wpointer-arith
                -Wunused -Woverloaded-virtual   dumy526.cc  -o dumy526
                -L../../bag  -lbag_i686  -lgmpxx -lgmp

real    0m2.235s
user    0m1.992s
sys 0m0.208s

  2 ^  0  size: 1  1  sum : 1
  2 ^  1  size: 1  2  sum : 2
  2 ^  2  size: 1  4  sum : 4
  2 ^  3  size: 1  8  sum : 8
  2 ^  4  size: 2  16  sum : 7
  2 ^  5  size: 2  32  sum : 5
  2 ^  6  size: 2  64  sum : 10
  2 ^  7  size: 3  128  sum : 11
  2 ^  8  size: 3  256  sum : 13
  2 ^  9  size: 3  512  sum : 8
  2 ^ 10  size: 4  1,024  sum : 7
  2 ^ 11  size: 4  2,048  sum : 14
  2 ^ 12  size: 4  4,096  sum : 19
  2 ^ 13  size: 4  8,192  sum : 20
  2 ^ 14  size: 5  16,384  sum : 22
  2 ^ 15  size: 5  32,768  sum : 26
  2 ^ 16  size: 5  65,536  sum : 25

  2 ^ 1000  size: 302  

10,715,086,071,862,673,209,484,250,490,600,018,105,614,048,117,055,336,074,437,
503,883,703,510,511,249,361,224,931,983,788,156,958,581,275,946,729,175,531,468,
251,871,452,856,923,140,435,984,577,574,698,574,803,934,567,774,824,230,985,421,
074,605,062,371,141,877,954,182,153,046,474,983,581,941,267,398,767,559,165,543,
946,077,062,914,571,196,477,686,542,167,660,429,831,652,624,386,837,205,668,069,
376

  sum-of-digits: 1366


  duration: 4,569 us

  FINI   4616 us

---

JFF (just for fun) and because it is easy with the mpz_class:

2 ^ 10000  size: 3011  

19,950,631, ... ,596,709,376

sum-of-digits: 13,561



2 ^ 100000  size: 30103  

9,990,020, ... ,883,109,376

sum-of-digits: 135,178