Fastest way to find the sum of decimal digits

Question

What is the fastest way to find the sum of decimal digits? The following code is what I wrote but it is very very slow for range 1 to 1000000000000000000

long long sum_of_digits(long long input) {
    long long total = 0;
    while (input != 0) {
        total += input % 10;
        input /= 10;
    }
    return total;
}

int main ( int argc, char** argv) {
    for ( long long i = 1L; i <= 1000000000000000000L; i++) {
        sum_of_digits(i);
    }
    return 0;
}

Answer 1

I'm assuming what you are trying to do is along the lines of

#include <iostream>
const long long limit = 1000000000000000000LL;
int main () {
   long long grand_total = 0;
   for (long long ii = 1; ii <= limit; ++ii) {
      grand_total += sum_of_digits(i);
   }
   std::cout << "Grand total = " << grand_total << "\n";
   return 0;
}

This won't work for two reasons:

• It will take a long long time.
• It will overflow.

To deal with the overflow problem, you will either have to put a bound on your upper limit or use some bignum package. I'll leave solving that problem up to you.

To deal with the computational burden you need to get creative. If you know the upper limit is limited to powers of 10 this is fairly easy. If the upper limit can be some arbitrary number you will have to get a bit more creative.

First look at the problem of computing the sum of digits of all integers from 0 to 10ⁿ-1 (e.g., 0 to 9 (n=1), 0 to 99 (n=2), etc.) Denote the sum of digits of all integers from 10ⁿ-1 as S_n. For n=1 (0 to 9), this is just 0+1+2+3+4+5+6+7+8+9=45 (9*10/2). Thus S₁=45.

For n=2 (0 to 99), you are summing 0-9 ten times and you are summing 0-9 ten times again. For n=3 (0 to 999), you are summing 0-99 ten times and you are summing 0-9 100 times. For n=4 (0 to 9999), you are summing 0-999 ten times and you are summing 0-9 1000 times. In general, S_n=10S_n-1+10^n-1S₁ as a recursive expression. This simplifies to S_n=(9n10ⁿ)/2.

If the upper limit is of the form 10ⁿ, the solution is the above S_n plus one more for the number 1000...000. If the upper limit is an arbitrary number you will need to get creative once again. Think along the lines that went into developing the formula for S_n.

Answer 2

You can break this down recursively. The sum of the digits of an 18-digit number are the sums of the first 9 digits plus the last 9 digits. Likewise the sum of the digits of a 9-bit number will be the sum of the first 4 or 5 digits plus the sum of the last 5 or 4 digits. Naturally you can special-case when the value is 0.