11
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ Please try to update your title to reflect what it is your code does, not what improvements you want to make. \$\endgroup\$ – forsvarir May 29 '16 at 18:36
  • \$\begingroup\$ Is this any better, @forsvarir? \$\endgroup\$ – sxbrentxs May 29 '16 at 18:47
  • 1
    \$\begingroup\$ Yes, the title change and addition of the function spec make your question much more engaging. \$\endgroup\$ – forsvarir May 29 '16 at 19:03
7
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ > Why m / 3? Why do you need the inner loop? Apologies, that was/is a remainder of me trying to get the code to execute fully on DotNETFiddle. And the loop was more to calculate the volume. But That's not needed anymore. Thanks for this. Could you tell me, though why n * n * n is better over Math.Pow? \$\endgroup\$ – sxbrentxs May 29 '16 at 19:23
  • 1
    \$\begingroup\$ @sxbrentxs Math.Pow is intended for floating point math. You need only two integer multiplications, while Math.Pow calculates it as Exp(y * Log(x)) and also you need to cast arguments to double and back. \$\endgroup\$ – Dmitry May 29 '16 at 19:33
  • \$\begingroup\$ Which makes Math.Pow obsolete and slow in this case. Cool! Thank you. \$\endgroup\$ – sxbrentxs May 29 '16 at 19:34
26
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Holy shit. That's a lot to take in. I think I know what you did and what I have to do. Thank you! \$\endgroup\$ – sxbrentxs May 29 '16 at 19:27
  • \$\begingroup\$ Wow! Very impressed to see an O(1) solution. +1. \$\endgroup\$ – ApproachingDarknessFish May 31 '16 at 0:58
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.