Max-digits of digit summing

Question

As a challenge I decided to do the following problem:

How many different numbers with n digits are there whose digits add up to k?

As this is an embarrassingly parallel problem I decided to use a bit of GPGPU programming (partly for learning purposes) using C++AMP and came up with the following solution:

#include <iostream>
#include <vector>
#include <assert.h>
#include <amp.h>
#include <chrono>
#include <ctime>
#include <numeric>

inline unsigned int AddDigits( unsigned int n ) restrict(amp, cpu)
{
        unsigned int sum = 0;
        while( n > 0 )
        {
                sum += n % 10;
                n /= 10;
        }

        return sum;
}

int main()
{
        std::chrono::steady_clock clock;
        unsigned int iSize, iSumRequired;

        std::cout << "Please enter the number of digits: ";
        std::cin >> iSize;
        std::cout << std::endl << "Please enter the sum required: ";
        std::cin >> iSumRequired;
        std::cout << std::endl;

        unsigned long long iMaxNum = std::pow( 10, iSize );

        assert( vecData.max_size() > iMaxNum );

        std::vector<unsigned int> vecData( iMaxNum );
        std::vector<int> vecNumValid( iMaxNum );

        auto tpBegin = clock.now();
        std::iota( vecData.begin(), vecData.end(), 1 );

        concurrency::array_view<const unsigned int, 1> arrayView( iMaxNum, vecData );
        concurrency::array_view<int, 1> numValid( iMaxNum, vecNumValid );

        concurrency::parallel_for_each( numValid.extent, [=]( concurrency::index<1> idx ) restrict( amp ) {
                numValid[idx] = (AddDigits( arrayView[idx] ) == iSumRequired ? 1 : 0);
        } );

        numValid.synchronize();

        int iNumValid = concurrency::parallel_reduce( vecNumValid.begin(), vecNumValid.end(), 0 );

        std::cout << "The number of valid numbers are: " << iNumValid << std::endl;
        auto tpTimeTaken = clock.now() - tpBegin;

        std::cout << "Time Taken: " << std::chrono::duration_cast<std::chrono::milliseconds>(tpTimeTaken).count() << std::endl;

        return 0;
}

This offers a significant improvement over parallel brute-forcing on the CPU (2x speedup versus 8 threads on an 8-core CPU), however out of curiosity I was wondering whether any further speedup could be gained, perhaps through somehow running the parallel_reduce on the GPU rather than on the CPU; removing the necessity to synchronize the array_view?

Moreover, this only allows for up to 8-digits (because of the restriction of the maximum value being less than 2³¹-1) because the GPU only supports types of float, double, int, unsigned int and bool; is there a way to circumvent this and improve the maximum number of digits allowed?

Answer 1

I agree with @Christopher. The brute force might be embarrassingly parallel, but its complexity is dreadful.

Calling f(n,k) the answer, there is a simple approach : the case n>1 boils down to sum (g(n-1,k-i) for i in [1..min(k,9)]), where g also allows i=0. The case n=1 is left as an exercise, and some other early stop shortcuts might be used.

With this algorithm, you don't even need C++. Instead, a language with lightweight threads (scala) will prove profitable, since up to 9^n threads may be instantiated.

Answer 2

I understand that you are asking from a parallel point of view, but I am unable to provide feedback on that, as I have never worked with this system before. But from my point of view, creating a parallel solution is has been done premature.

Prior to creating a parallel solution to speed up your solution, you should improve the efficiency of the algorithm. At present you consider all numbers in the range of [1, 10^N), whereas you only need to evaluate numbers where the number of digits in the number is equal to N. In which case you only need to evaluate numbers in the range of [10^N-1, 10^N).

You could further improve this via considering permutations and combinations. This would allow you to calculate all the different combinations of the digits for the given range. Once you have these you can then check which of the combinations digits sum to the required total.

If X combinations sum to a given total then you can quickly calculate how many numbers within the require range have N digits and sum to the goal. By computing X * (N Perm N) where N is the number of digits and where permutations are calculated without replacement. Representing just the N digits in the solution.

At this point you would be using a parallel solution to calculate the combination hits, but you may find the bottle neck of data transfer to a GPU causes the parallel solution to perform slower than the non-GPU enabled solution.