The 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 slow for the 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 assume you are trying to do this in lines

 #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 will not work for two reasons:

• It will take a lot of time.
• It will be an overflow.

To deal with the overflow problem, you will either have to set a limit on the upper limit, or use some kind of bignum package. I will leave the solution to this problem up to you.

To cope with the computational burden, you need to be creative. If you know that the upper limit is limited to a power of 10, this is pretty easy. If the upper limit can be some arbitrary number, you will have to work a little.

First, consider the problem of calculating the sum of the digits of all integers from 0 to 10 ⁿ -1 (for example, from 0 to 9 (n = 1), from 0 to 99 (n = 2)), etc.) Denote the sum of the digits of all integers numbers from 10 ⁿ -1 as S _n . For n = 1 (0 to 9), it's just 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45 (9 * 10/2). Thus, S ₁ = 45.

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

If the upper limit is 10 ⁿ then the solution is above S _n plus one more for the number 1000 ... 000. If the upper limit is an arbitrary number, you will need to create an advertisement again. Think along the lines that went into the development of the formula for S _n .

Answer 2

Reading your edit: It takes a long time to calculate this function in a loop for I between 1 and 1,000,000,000,000,000,000. It's not a problem.

1000000000000000000 - one billion billion. Your processor can do at best billions of operations per second. Even with a non-historical 4-5 GHz processor, and if you take the best case, it comes down to adding, mod, div and a comparison jump, you can only do 1 billion iterations per second, that is, it will take about 1 billion seconds.

Answer 3

You can break it down recursively. The sum of the digits of an 18-digit number is the sum of the first 9 digits plus the last 9 digits. Similarly, 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 use the special case when the value is 0.

Answer 4

You probably don't want to do this with brute force. This seems to be a more logical question.

Note - 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = N (N + 1) / 2 = 45.

---- Modifying the answer to make it understandable after David's comment

See David's answer - I was wrong

Answer 5

I think you cannot do better than O(N) , where N is the number of digits in the given number (which is not expensive)

However, if I understand your question (range) correctly, you want to display the sum of the digits for the range of numbers. In this case, you can increase by one when you go from number0 to number9, and then decrease by 8.

Answer 6

You need to cheat - find math patterns that will allow you to cut back on your calculations.

• For example, do you really need to check this entry each time? = 0? Does it matter if you add 0/10 several times? Since this does not matter, consider rolling out a loop.
• Can you perform calculations in a larger base, for example, bases 10 ^ 2, 10 ^ 3, etc., which can allow you to reduce the number of digits that you will need to convert back to base 10? If this works, you can implement the cache faster.
• Consider the capabilities of built-in compilers that allow you to give hints to the compiler for branch prediction.
• Given that this is C ++, think about it using metaprogramming templates.
• Given that sum_of_digits is purely functional, consider caching results.

Now most of these suggestions will have unpleasant consequences - but I want to say that if you have reached the limit of what your computer can do for this algorithm, you need to find another solution.

This is probably a great starting point if you want to learn more about this: http://mathworld.wolfram.com/DigitSum.html

Answer 7

Option 1:

You can do this faster by submitting the result of one iteration of the loop to the next iteration.

For example, if i == 365 , the result is 14 . In the next cycle, i == 366 - 1 is greater than the previous result. The sum is also 1: 3 + 6 + 6 = 15 .

Problems arise when there is a carry digit. If i == 99 (i.e., Result = 18), the next loop result is not 19, it is 1. You will need additional code to detect this case.

Opportunity 2:

Thinking, though above, it occurred to me that the sequence of results from sum_of_digits would look like a sawtooth when plotting. With some analysis of the graph (which I leave as an exercise for the reader), it may be possible to determine a method that allows direct calculation of the result of the sum.

However, as some others pointed out: even with the maximum possible implementation of sum_of_digits and the most optimized loop code, you cannot calculate the results of 1,000,000,000,000,000,000 in any useful timeframes and, of course, in no less than one second.

Answer 8

Pretty late to the party, but anyway, here is my solution. Sorry in Python, not C ++, but it needs to be relatively easy to translate. And since this is primarily a problem with the algorithm, I hope this is normal.

As for the overflow problem, the only thing that comes to mind is to use arrays of numbers instead of actual numbers. Given this algorithm, I hope this does not affect the performance too much.

https://gist.github.com/frnhr/7608873

He uses these three recursions, which I found by looking and sticking out the problem. Instead, trying to come up with some general and secret equations, here are three examples. From this one can easily see the general case.

ratio 1

Reduces function calls with an arbitrary argument by several recursive calls with more predictable arguments for use in relations 2 and 3.

 foo(3456) == foo(3000) + foo(400) + 400 * (3) + foo(50) + 50 * (3 + 4) + foo(6) + 6 * (3 + 4 + 5) 

ratio 2

Reduce calls with an argument of the form L*10^M (for example: 30, 7000, 900000) for a recursive call suitable for relation 3. These triangular numbers popped up completely uninvited (but welcome) :)

 triangular_numbers = [0, 1, 3, 6, 10, 15, 21, 28, 36] # 0 not used foo(3000) == 3 * foo(1000) + triangular_numbers[3 - 1] * 1000 

Only useful if L > 1 . This is true for L = 1 , but trivial. In this case, go directly to ratio 3.

ratio 3

Recursively reduce calls with an argument in the format 1*10^M by a call with an argument divided by 10.

 foo(1000) == foo(100) * 10 + 44 * 100 + 100 - 9 # 44 and 9 are constants 

Ultimately, you only need to calculate the sum or numbers for numbers from 0 to 10, and it turns out that only up to 3 of these calculations are needed. Everything else will take care of this recursion. I am sure it works in O(logN) time. This is FAAST !!!!! 11one

On my laptop, it calculates the sum of the digits of the sum for a given number with more than 1300 digits in less than 7 seconds! Your test (1000000000000000000) is calculated in 0.000112057 seconds!

Answer 9

Edit: It seems you want the sum of actual numbers to be: 12345 = 1 + 2 + 3 + 4 + 5, not the number of digits, but also the sum of all numbers from 1 to 12345 (inclusive);

As quickly as possible, you can:

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

What else will be slow if you do enough iterations. Your requirements in the amount of 1,000,000,000,000,000,000 iterations are one million, one million, one million. Given that 100 million people consume about 10,000 ms on my computer, you can expect it to take 100 ms for 1 million records, and you want to do it another million million times. There are only 86,400 seconds per day, so at best we can calculate about 86,400 million records per day. It takes one computer

Suppose your method can be executed in a single floating point operation (somehow), suppose you are using computer K, which is currently the fastest (Rmax) supercomputer with more than 10 petaflops if you do the math which equals = 10,000 million Million floating operations per second. This means that your cycle is 1 million, one million, one million will take the fastest unallocated supercomputer in the world for 100 seconds to calculate the sums (if 1 floating point operation was performed for the calculation, which cannot be), so you will need to wait for quite a long time for computers to become so powerful that your solution can work under one second.

Whatever you try to do, you are either trying to solve an insoluble problem in almost real time (for example, those related to graphics), or you misunderstand the question / task you asked, or you expect something faster to complete than any (unallocated) computer system.

If your task is to actually sum all the digits of the range when displayed and then output them, the answer should not improve the for loop. eg:

 1 = 0 10 = 46 100 = 901 1000 = 13501 10000 = 180001 100000 = 2250001 1000000 = 27000001 10000000 = 315000001 100000000 = 3600000001 

From this, you could work out a formula to actually calculate the total sum of all digits for all numbers from 1 to N. But it is not clear what you really want, for a much faster computer.

Answer 10

There is no better but simpler:

 int DigitSumRange(int a, int b) { int s = 0; for (; a <= b; a++) for(c : to_string(a)) s += c-48; return s; } 

Answer 11

If you want to find the sum for the range from 1 to N, just follow these

 long sum = N(N+1)/2; 

This is the fastest way.

Answer 12

The formula for finding the sum of the digits of numbers from 1 to N:

(1 + N) * (N / 2)

http://mathforum.org/library/drmath/view/57919.html

There is a class written in C # that supports a number with a greater than the supported max-limit long. You can find it here. Oyster.Math

Using this class, I generated a block of code in C #, it may be useful to you.

 using Oyster.Math; class Program { private static DateTime startDate; static void Main(string[] args) { startDate = DateTime.Now; Console.WriteLine("Finding Sum of digits from {0} to {1}", 1L, 1000000000000000000L); sum_of_digits(1000000000000000000L); Console.WriteLine("Time Taken for the process: {0},", DateTime.Now - startDate); Console.ReadLine(); } private static void sum_of_digits(long input) { var answer = IntX.Multiply(IntX.Parse(Convert.ToString(1 + input)), IntX.Parse(Convert.ToString(input / 2)), MultiplyMode.Classic); Console.WriteLine("Sum: {0}", answer); } } 

Please ignore this comment if it is not appropriate for your context.