Calculating the amount of cubes needed to form a sum

Question

Since I've never done any performance programming (Aside from the better choices such as array vs list etc. The real basics.), I should probably read up on it. But I had to start somewhere, so, someone I know - which is a much better programmer than I am - tasked me with making this "assignment":

You are given the total volume m of the building. Being given m can you find the number n of cubes you will have to build?

The parameter of the function findNb (find_nb, find-nb) will be an integer m and you have to return the integer n such as \$n^3 + (n-1)^3 + \dots + 1^3 = m\$ if such a n exists or -1 if there is no such n.

He gave me this template with it:

using System;

public class Program
{
    public static void Main()
    {
        Console.WriteLine(findNb(4183059834009));
        Console.WriteLine(findNb(24723578342962));
        Console.WriteLine(findNb(135440716410000));
        Console.WriteLine(findNb(40539911473216));
    }

    public static long findNb(long m)
    {

    }
}

In which I inserted:

for(long n = 1; n < (m / 3); n++)
{
    double vol = 0;
    for(long i = 0; i < n; i++)
        vol += Math.Pow((n - i), 3);

    if(vol > m)
        return -1;

    if(vol == m)
        return n;
}
return -1;

This code works, but it takes incredibly long for the larger numbers, as is my main problem.

What can I do to shorten the time it takes for this code takes to complete?

Answer 1

First of all, you have a bug:
variable vol is declared as double that causes the condition vol == m hardly to be satisfied.

Next, you don't need the Math.Pow method, you could relace it with just n * n * n.
And your loops look a bit confusing. Why m / 3? Why do you need the inner loop?

The proposed code:

private static long findNb(long m)
{
    long n = 1;
    long vol = 0;
    while (vol < m)
    {
        vol += n * n * n;

        if (vol == m)
            return n;

        ++n;
    }
    return -1;
}

Answer 2

When there's math to be done, always check if some formula exists

$$1^3+2^3 + \dots+n^3 = m = (1+2 + \dots+n)^2$$

in conjunction with some other formula (interesting wikipedia article title)

$$\sum^n_{k=1}k = \frac{n(n+1)}{2}$$

you get some equation for the result

$$\sqrt{m} = 1+2 + \dots+n = \sum^n_{k=1}k = \frac{n(n+1)}{2}$$ and maybe some closed formula

$$ \begin{align} \sqrt{m} &= \frac{n(n+1)}{2}\\ 2\sqrt{m} &= n(n+1)\\ 2\sqrt{m} &= n^2+n\\ 0&= n^2+n - 2\sqrt{m} \end{align} $$

Which has the 2 solutions

$$n_{1,2} = -\frac12 \pm\sqrt{\frac14+2\sqrt{m}}$$

As \$n\$ should be a positive number, only the first solution makes sense.

Return \$ -\frac12 +\sqrt{\frac14+2\sqrt{m}}\$ if it is an integer or \$-1\$ otherwise.

The results are:

$$ \begin{array}{r|r} m & n\\ \hline 4183059834009 & 2022\\ 24723578342962 & -1\\ 135440716410000 & 4824\\ 40539911473216 & 3568\\ \end{array} $$

24723578342962 is a very close call, because

$$\sum^{3153}_{k=1}k^3=24723578342961$$

is only 1 off. The floating point result is \$n=3153.00000000003\$. If you don't want to get false positives due to floating point precision (lack thereof), you can do the check by converting the result to some integer type and see if you get the exact number by doing the calculations with that.

Answer 3

For a significant speedup: In the outer loop, you vary n from 1 to some large value, and in the inner loop you add up n values.

Now in the next iteration of the outer loop, using n+1 instead of n, you run the inner loop again, this time adding up n+1 value. But just before that, in the previous loop, you already added up n values, so to get the sum of n+1 values, all you have to do is add value number n+1 to the sum that you already have.

Have a variable n and a variable sum_n. sum_n will be the sum of the first n cubes. Initially n = 0 and sum_n = 0. Inside the outer loop, increase n by 1 then increase sum_n by nnn.

For example, if n goes from 1 to 1000, you add up one value, then two, then three, and so on, and eventually you add up 1000 values. On average about 500. This change means you add only one value in each iteration of the outer loop.

This is an improvement that works for any task where you calculate consecutive sums. In this particular case, you can find a formula to calculate the sum. That isn't helpful by itself, since calculating the formula is likely slower than calculating the sums. However, you can reverse the formula and calculate what n should be, and then you just have to verify this. So you just need a small fixed number of operations, independent of the size of the m that you were given.