7
\$\begingroup\$

I tried to solve Project Euler 12 with a first very naive solution by myself. It took nearly 30 minutes to run until it found the solution. Then I made a change in the function getDivisorCount which should have made the run time to about the square root of the original code, about 5 minutes. At least this was my opinion because the complexity should have changed from \$O(n^2)\$ to \$O(n\sqrt n)\$. But it went down to less than a second which surprised me and I could not find a reason.

Here is my code for review, a second time:

#include <iostream>
#include <math.h>

using namespace std;

int getDivisorCount(unsigned int number)
{
    unsigned int count = 0;
    unsigned int sqrt_ = sqrt(number);
    for(unsigned int i = 1; i <= sqrt_; i++)
    {
        if((number % i) == 0)
            count+=2;
    }
    if (sqrt_ * sqrt_ == number)
    {
        count--;
    }
    return count;
}

int main()
{
    unsigned int number = 0;
    for (unsigned int i = 1; ; i++)
    {
        number+=i;
        if(getDivisorCount(number)>500)
            break;
    }
    cout << number;
    return 0;
}

Note that my first version used the method:

int getDivisorCount(unsigned int number)
{
    unsigned int count = 0;
    for(unsigned int i = 1; i <= number; i++)
    {
        if((number % i) == 0)
            count++;
    }
    return count;
}

Both compiled with g++ -O2.

I'm looking for a fresh code review, but an explanation of why the current version is so much faster would also be appreciated.

\$\endgroup\$
  • \$\begingroup\$ The execution time difference is (n sqrt(n))/n²=sqrt(n) and for n = 76576500 sqrt(n)~8750 and 30 min/8750 ~ 0.2 sec so the speed is not particulary surprising. \$\endgroup\$ – Siphor Dec 27 '14 at 13:56
  • \$\begingroup\$ Although not so important in this case remember that big O notation just tells you how the same algorithm scales with problem size, not which of a number of algorithms is necessarily faster. The size of the constants before n^2, n etc. can dominate. \$\endgroup\$ – James Elderfield Dec 28 '14 at 0:16
6
\$\begingroup\$

Brythan has given a good review of the code, but I am going to disagree with his analysis of the complexity.... or, at least part of his analysis.

'Complexity' is an indication of how the algorithm scales with respect to 'size'. How much additional time is required to compute a solution if the input data is X times larger. An algorithm with \$O(n)\$ time complexity, that runs in T seconds with X data, will require 2T seconds to run with 2X data.

How does this relate to your problem? Well, it doesn't. Not at all. Your inputs are not changing at all.

The solution to the problem "the first number that has 500 divisors" results in a number somewhat larger than 75,000,000. That is somewhat after the 12-thousandth triangle number.

So, in this case, you are looping through 12,000 times, and that's the same regardless of whether you use your old, or your new getDivisorCount method.

The question is, why is the new one so much faster? Well, that's simple....

As your numbers become reasonably large, say, around 70,000,000, you are, in your old loop, going to loop 70,000,000 times.

In the new code, you are going to loop less than 8,500 times. Now, that is..... about 10,000 times faster.

If you were to take the getDivisorCount method itself as an isolated system, the performance complexity of the original code was \$O(n)\$ where n is the input number. for the new algorithm, the complexity is \$O(\sqrt{n})\$. Since 'n' is, for the most part, a very large number, the difference between \$n\$ and \$\sqrt{n}\$ is huge.

It does not surprise me that the second solution is thousands of times faster, for the large values you are factoring.

\$\endgroup\$
  • \$\begingroup\$ I found your analysis more understandable than Brythans because of the examples with the numbers (but this might also be because English is not my first language). I didnt expect that difference between i and number. I only tried the second version just for fun and didnt expect enough speed gain to go below 1 minute but the golden rule of optimization saved me: Always meassure. \$\endgroup\$ – sweet home Dec 27 '14 at 14:41
7
\$\begingroup\$

Nitpicks

using namespace std;

This can be a bad habit to start. See Why is using namespace std bad practice?

unsigned int sqrt_ = sqrt(number);

I don't like the name sqrt_. Something like sqrt_number would be better in my opinion.

unsigned int number = 0;
for (unsigned int i = 1; ; i++)
{
    number+=i;
    if(getDivisorCount(number)>500)
        break;
}

That's an odd way to write a loop. You are iterating i but never checking it. I would prefer something like

for ( unsigned int number = 1, i = 2; getDivisorCount(number) <= 500; number += i, i++ ) ;

That's rather dense -- it might be easier in a while loop. But at least this has a variable declaration, a loop check, and an increment. Also, it avoids having to break to exit the loop.

unsigned int number = 1;
unsigned int i = 2;
while ( getDivisorCount(number) <= 500 ) {
    number += i;
    i++;
}

Analysis

You refer to your original code as quadratic, but quadratic in what? The outer loop in main runs i times. The inner loop runs number times. What's number in terms of i? The answer is that number is quadratic in i. I.e. \$O(i^2)\$. So we actually run the inner loop in getDivisorCount \$O(i^3)\$ times.

The optimized loop only runs the square root of number times. But we know that the square root of number is about i. So overall, it runs \$O(i^2)\$ times.

So the difference between the two is about i in magnitude. What's i in this case? Well, without giving the exact answer, I'll tell you that it's over 10,000. You can get the exact answer by replacing

cout << number;

with

std::cout << i;

Note that you may have to move the declaration of i outside the loop.

Anyway, that's why your revised code is more than 10,000 times faster than your original code. That's how big i was.

More generally, when going from \$O(n^2)\$ to \$O(n)\$ in an otherwise similar algorithm, you don't take the square root of the time. You divide by n. In this case, i or number is n. This is why \$O(n)\$ is so much better than \$O(n^2)\$.

\$\endgroup\$
  • \$\begingroup\$ Thanks. Yes, most times I forget to delete the using from the project temmplates in the main file, especially in small projects like this. Your changed for loop was what also came to my mind but it looked too confusing to me and I try to avoid confusing code. The while loop didnt came into my mind because it was a counting loop and I automatically used for but it really looks better. \$\endgroup\$ – sweet home Dec 27 '14 at 14:22
  • \$\begingroup\$ Your analysis is wrong - well "wrong", saying both algorithms run in O(n!) is technically also correct, but a very loose upper bound. The first algorithm enters the inner loop \Sigma_{i=1}^Ni times where N is the first number that fits the criteria. This is equivalent to N(N+1)/2 or O(n^2). Or shortly said: The original analysis is correct, the improvement is only O(log n). \$\endgroup\$ – Voo Dec 27 '14 at 15:28
  • \$\begingroup\$ @Voo I didn't call \$N\$ the first number that met the criteria. I said it was the \$Nth\$ triangle number. If you change to your definition of \$N\$, then yes, the improvement is \$\sqrt N\$, but your \$N\$ is roughly the square of mine in magnitude. \$\endgroup\$ – Brythan Dec 27 '14 at 15:30
  • \$\begingroup\$ @Brythan You'll have to explain what i is exactly then, because the only input to the algorithm is to how high a number we loop - if that's not what you're picking what is it? The way I read it you're saying that the inner loop is run O(i^2) times with i at most being size N and that it is called N times. Both statements are true, but if you combine them you see that you can get a tighter bound. \$\endgroup\$ – Voo Dec 27 '14 at 15:39
  • \$\begingroup\$ @Voo No, i is the number of triangle numbers to get to 500 divisors. The original inner loop iterated \$i(i+1)/2\$ times on the \$i\$th iteration of the outer loop. The replacement iterates \$\sqrt {i(i+1)/2}\$ times. Under no circumstances is anything about this logarithmic, unless you are claiming that \$\frac{\sum_{n = 1}^i n(n+1)/2}{\sum_{n=1}^i \sqrt {n(n+1)/2}}\$ is \$O(\log i)\$. If that's your claim, you should write it out in an answer. \$\endgroup\$ – Brythan Dec 27 '14 at 16:03
5
\$\begingroup\$

Note that the \$i\$-th triangular number is \$\frac{i (i + 1)}{2}\$. If \$i\$ is even this is the product of the integers \$\frac{i}{2}\$ and \$(i + 1)\$; if \$i\$ is odd this is the product of the integers \$i\$ and \$\frac{(i + 1)}{2}\$.

If \$x\$ and \$y\$ have no common prime factors, as is the case here, the number of divisors is \$d (x * y) = d (x) * d (y)\$. So instead of calculating the number of divisors of a number \$x\$ around \$\frac{i^2}{2}\$ which works in \$O(\sqrt {i^2}) = O(i)\$, you calculate the number of divisors two numbers around \$i\$, which takes \$O(\sqrt i)\$.

That will give you another factor 100 for these small numbers and lets you get to much bigger numbers.

\$\endgroup\$
2
\$\begingroup\$

When you changed getDivisorCount(int) from \$O(n)\$ to \$O(\sqrt{n})\$, you made it a couple thousand times faster because the numbers you're trying to factor are in the millions.

But you can take it even further by recognizing that the prime factorization of each divisor of is a submultiset of the prime factorization of X and then enumerating those submultisets. Prime factorization is \$O(\sqrt{n})\$ in the worst case of trying to factor a prime, which is no worse than what you're currently doing, but it's faster for numbers with a lot of small prime factors because you can divide them out and eliminate a lot of search space.

For example, 60 = 2*2*3*5. This means each divisor is of the form 2x3y5z, where 0 ≤ x ≤ 2, 0 ≤ y ≤ 1, and 0 ≤ z ≤ 1. You have 3 choices for x, 2 for y, and 2 for z, and 3*2*2 = 12. This is the product of one more than each prime factor's multiplicity. Iterating all possibilities of x, y, and z gives all divisors without repeats:

  • 2x3050: 1, 2, 4
  • 2x3150: 3, 6, 12
  • 2x3051: 5, 10, 20
  • 2x3151: 15, 30, 60

My own implementation of Euler 12 in Python originally used a function essentially equivalent to your \$O(\sqrt{n})\$ getDivisorCount(int), and it took 37.5 seconds on an Atom N450. I switched it to enumerate submultisets of the prime factorization, and it took 2.4 seconds.

\$\endgroup\$
2
\$\begingroup\$

You should ask yourself: "What does it mean to take the square root of a time interval?" In particular, what are the units of the values involved?

If you measure time in minutes, then the square root of 30 minutes is 5.something sqrt(minutes), not 5.something minutes. But sqrt(minutes) doesn't correspond to any property of the real world, so the answer is meaningless.

This is made more obvious if you measure the same time in seconds; 30 minutes is 1800 seconds, and the square root is 42.something sqrt(seconds). You should immediately notice that 42 seconds is nowhere near 5 minutes, but the conversion factor between sqrt(seconds) and sqrt(minutes) is sqrt(60), ie. just under 8. So these two answers remain consistent.

Computers don't naturally count time in seconds, either - so let's try milliseconds, then microseconds. Your square roots are then 1342 sqrt(ms) and 42426 sqrt(µs).

You might want to look up "dimensional analysis" to help you avoid making such mistakes in future.

In fact, the ratio of time involved will be closer to the square root of the final answer you end up with, and is not related to the actual time taken at all. It's trivially easy to prove that any number with 500 divisors will be greater than 250^2, ie. 62500, so you should expect a speedup of at least 250x just from that, reducing an 1800-second run to just over 7 seconds.

\$\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.