Get sum of each digit below n as long

Question

This is the code I have but it's to slow, any way to do it faster.. the number range I'm hitting is 123456789 but I can't get it below 15 seconds, and I need it to get below 5 seconds..

long num = 0;

for (long i = 0; i <= n; i++)
{
    num = num + GetSumOfDigits(i);
}

static long GetSumOfDigits(long n)
{
    long num2 = 0;
    long num3 = n;
    long r = 0;
    while (num3 != 0)
    {
        r = num3 % 10;
        num3 = num3 / 10;
        num2 = num2 + r;
    }

    return num2;
}

sum =(n(n+1))/2 is not giving me the results I need, not calculating properly..

For N = 12 the sum is 1+2+3+4+5+6+7+8+9+(1+0)+(1+1)+(1+2)= 51. I need to do this with a formula instead of a loop..

I've got about 15 tests to run through each under 6 seconds..

with parallel I got one test from 15seconds to 4-8 seconds..

Just to show you the test I'm doing this is the hard one..

[Test]
public void When123456789_Then4366712385()
{
   Assert.AreEqual(4366712385, TwistedSum.Solution(123456789));
}

On my computer I can run all the tests under 5 seconds.. Look at the photo..

With DineMartine Answer I got these results:

Answer 1

Your algorithm complexity is N log(N). I have found a better algorithm with complexity log(N). The idea is to iterate on the number of digits which is :

log10(n) = ln(n)/ln(10) = O(log(n)).

The demonstration of this algorithm involves a lot of combinatorial calculus. So I choose not to write it here.

Here is the code :

public static long Resolve(long input)
{
    var n = (long)Math.Log10(input);
    var tenPow = (long)Math.Pow(10, n);
    var rest = input;
    var result = 0L;
    for (; n > 0; n--)
    {
        var dn = rest / tenPow;
        rest = rest - dn * tenPow;
        tenPow = tenPow / 10;
        result += dn * (rest + 1) + dn * 45 * n * tenPow + dn * (dn-1) * tenPow * 5 ;
    }

    result += rest * (rest + 1) / 2;

    return result;
}

Now you would solve the problem in a fraction of second.

The idea is to write the input as a list of digit :

Assuming the solution is given by a function f, we are looking for g a recursive expression of f over n :

Actually g can be written as follow :

If you find h, the problem would be practically solved.

Answer 2

A little bit convoluted but gets the time down to practicaly zero:

    private static long getSumOfSumOfDigitsBelow(long num)
    {
        if (num == 0)
            return 0;
        // 1 -> 1 ; 12 -> 10; 123 -> 100; 321 -> 100, ...
        int pow10 = (int)Math.Pow(10, Math.Floor(Math.Log10(num)));
        long firstDigit = num / pow10;
        long sum = 0;
        var sum999 = getSumOfSumOfDigitsBelow(pow10 - 1);
        var sumRest = getSumOfSumOfDigitsBelow(num % pow10);
        sum += (firstDigit - 1)*(firstDigit - 0)/2*pow10 + firstDigit*sum999;
        sum += firstDigit*(num%pow10 + 1) + sumRest;
        return sum;
    }


    getSumOfSumOfDigitsBelow(123456789) -> 4366712385 (80us)
    getSumOfSumOfDigitsBelow(9223372036854775807) -> 6885105964130132360 (500us - unverified)

The trick is to avoid to compute the same answer again and again. e.g. 33:

your approach:

sum = 1+2+3+4+5+6+7+8+9+(1+0)+(1+1)+(1+2)+ ... +(3+2)+(3+3)

my approach:

sum = 10*(0 + (1+2+3+4+5+6+7+8+9)) + 
   10*(1 + (1+2+3+4+5+6+7+8+9)) + 
   10*(2 + (1+2+3+4+5+6+7+8+9)) + 
   3*(3 + (1 + 2 + 3))

The (1+2+3+4+5+6+7+8+9)-part have to be calculated only once. The loop of 0..firstDigit-1 can be avoided by the n(n-1)/2-trick. I hope this makes sense.

The complexity is O(2^N) with N counting the number of digits. This looks very bad but is fast enough for your threshold of 5s even for long-max. It may be possible to transform this algorithm in something running in O(n) by calling getSumOfSumOfDigitsBelow() only once but it would look much more complex.

First step of optimization: look at your algorithm ;)

---

Comming back to this problem after the answer of DineMartine :

To further optimize the algorithm, the sum999-part can be replaced by an explicit formula. Lets take some number 9999...9=10^k-1 into the code and replace accordingly:

sum(10^k-1) = (9 - 1)*(9 - 0)/2*pow10 + 9*sum999 + 9*(num%pow10 + 1) + sumRest
sum(10^k-1) = 36*pow10 + 9*sum999 + 9*(num%pow10 + 1) + sumRest

sum999 and sumRest are the same for the numbers of type 10^k:

sum(10^k-1) = 36*pow10 + 10*sum(10^(k-1)-1) + 9*(num%pow10 + 1)
sum(10^k-1) = 36*pow10 + 10*sum(10^(k-1)-1) + 9*((10^k-1)%pow10 + 1)
sum(10^k-1) = 36*pow10 + 10*sum(10^(k-1)-1) + 9*pow10
sum(10^k-1) = 45*pow10 + 10*sum(10^(k-1)-1)

We have a definition of sum(10^k-1) and know sum(9)=45. And we get:

sum(10^k-1) = 45*k*10^k

The updated code:

    private static long getSumOfSumOfDigitsBelow(long num)
    {
        if (num == 0)
            return 0;
        long N = (int) Math.Floor(Math.Log10(num));
        int pow10 = (int)Math.Pow(10, N);
        long firstDigit = num / pow10;
        long sum = (firstDigit - 1)*firstDigit/2*pow10 
            + firstDigit* 45 * N * pow10 / 10 
            + firstDigit*(num%pow10 + 1) 
            + getSumOfSumOfDigitsBelow(num % pow10);
        return sum;
    }

This is the same algorithm as the one from DineMartine but expressed in a recursive fashion (I've compared both implementations and yes I'm sure it is ;) ). The runtime goes down to practically zero and the time complexity is O(N) counting the number of digits or O(long(N)) taking the value.

Answer 3

If you have multiple processors (or cores) in your system, you can speed it up quite a lot by doing the calculations in parallel.

The following code demonstrates (it's a compilable console app).

The output when I try it on my system (4 cores with hyperthreading) is as follows for a release build:

x86 version:

Serial took: 00:00:14.6890714
Parallel took: 00:00:03.5324480
Linq took: 00:00:04.4480217
Fast Parallel took: 00:00:01.6371894

x64 version:

Serial took: 00:00:05.1424354
Parallel took: 00:00:00.9860272
Linq took: 00:00:02.6912356
Fast Parallel took: 00:00:00.4154711

Note that the parallel version is around 4 times faster. Also note that the x64 version is MUCH faster (due to the use of long in the calculations).

The code uses Parallel.ForEach along with a Partitioner to split the range of number into sensible regions for the number of processors available. It also uses Interlocked.Add() to quickly add the numbers with efficient locking.

I've also added another method where you need to pre-calculate the sums for the numbers between 0 and 1000. You should only need to pre-calculate the sums once for each run of the program. See FastGetSumOfDigits().

Using FastGetSumOfDigits() more than doubles the previous fastest time on my PC. You can increase the value of SUMS_SIZE to a larger multiple of 10 to increase the speed still further, at the expense of space. Increasing it to 10000 on my PC decreased the time to ~0.3s

(The sums array only needs to be a short array, to save space. It doesn't need a larger type.)

using System;
using System.Collections.Concurrent;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Threading;
using System.Threading.Tasks;

namespace Demo
{
    internal class Program
    {
        public static void Main()
        {
            long n = 123456789;

            Stopwatch sw = Stopwatch.StartNew();
            long num = 0;

            for (long i = 0; i <= n; i++)
                num = num + GetSumOfDigits(i);

            Console.WriteLine("Serial took: " + sw.Elapsed);
            Console.WriteLine(num);

            sw.Restart();
            num = 0;
            var rangePartitioner = Partitioner.Create(0, n + 1);

            Parallel.ForEach(rangePartitioner, (range, loopState) =>
            {
                long subtotal = 0;

                for (long i = range.Item1; i < range.Item2; i++)
                    subtotal += GetSumOfDigits(i);

                Interlocked.Add(ref num, subtotal);
            });

            Console.WriteLine("Parallel took: " + sw.Elapsed);
            Console.WriteLine(num);

            sw.Restart();
            num = Enumerable.Range(1, 123456789).AsParallel().Select(i => GetSumOfDigits(i)).Sum();
            Console.WriteLine("Linq took: " + sw.Elapsed);
            Console.WriteLine(num);

            sw.Restart();
            initSums();
            num = 0;

            Parallel.ForEach(rangePartitioner, (range, loopState) =>
            {
                long subtotal = 0;

                for (long i = range.Item1; i < range.Item2; i++)
                    subtotal += FastGetSumOfDigits(i);

                Interlocked.Add(ref num, subtotal);
            });

            Console.WriteLine("Fast Parallel took: " + sw.Elapsed);
            Console.WriteLine(num);
        }

        private static void initSums()
        {
            for (int i = 0; i < SUMS_SIZE; ++i)
                sums[i] = (short)GetSumOfDigits(i);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static long GetSumOfDigits(long n)
        {
            long sum = 0;

            while (n != 0)
            {
                sum += n%10;
                n /= 10;
            }

            return sum;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static long FastGetSumOfDigits(long n)
        {
            long sum = 0;

            while (n != 0)
            {
                sum += sums[n % SUMS_SIZE];
                n /= SUMS_SIZE;
            }

            return sum;
        }

        static short[] sums = new short[SUMS_SIZE];

        private const int SUMS_SIZE = 1000;
    }
}