Making a loop faster

Question

I want to calculate if a number is a perfect number (sum(proper divisors) == number). So all I have to do is get the proper divisors, add them up and look if it's the number. For this I use a for-loop:

cin >> number;
sum = 1;
for (int i = number/2; i > 1; --i) {
  if (number % i == 0) {
    sum = sum + i;
  }
  if (sum > number) {break;}
}
if (sum == number) {cout << "perfect!" << endl;}

This loop is too slow. What I have done already as you can see is break out of the loop if the sum is already bigger than the number, I start from higher numbers (so if the sum is greater, it gets there faster), and since 1 is always a proper divisor, I don't need to loop over it.

Now I'm kind of out of ideas and would really appreciate some tips on how to improve this loop further (or even a completely different approach?)

One possible trick - instead of starting from `number/2`, start from `sqrt(number)`. Observe that, if `i` is a divisor, then `number/i` is too, so you only need to visit the smaller of the two. — Igor Tandetnik, Jun 25 '16 at 16:09
@nwp Not so, or at least, not trivially. `28=1+2+4+7+14` is a perfect number, but 4 is not prime. — Igor Tandetnik, Jun 25 '16 at 16:10
Even easier trick would be to simply hard-code all the perfect numbers. There are only [five or six](https://oeis.org/A000396) that would fit into a 32-bit int, and just a couple more that fit into 64-bit one. — Igor Tandetnik, Jun 25 '16 at 16:12
sqrt(number) can't work for all cases. If you have for example number=6, the iteration would start with 2, so you omit the proper divisor 3. — Fl.pf., Jun 25 '16 at 16:13
@Nils_S Like I said, you just need to sum up both `divisor` and `number/divisor`. So when you visit 2, you add 2 and 3. — Igor Tandetnik, Jun 25 '16 at 16:14
@Igor Tandetnik hard-coding would do the trick. But that depletes the purpose of the exercise :) Ah you are right. I'll try that now — Fl.pf., Jun 25 '16 at 16:16

score 4 · Accepted Answer · answered Jun 25 '16 at 16:20

You can get a very large improvement in the following way:

cin >> number;
sum = 1;
for (int i = sqrt(number); i > 1; --i) {
  if (number % i == 0) {
    sum += i + (number / i);
  }
  if (sum > number) {break;}
}
if (sum == number) {cout << "perfect!" << endl;}

As you can see, this loop starts at the square root of the input, instead of half the input. This gives an O(sqrt(N)) improvement in the worst case. For any pair of divisors of a number, one must lie above the square root and one most lie below. Another important thing to be aware of is that integer division/modulus is very expensive, but when they are computed, both are computed simultaneously. That means that once you have computed number % i, number / i is basically free. Hence, the cost of each iteration in my code is basically identical to the cost per iteration in yours, but there are many fewer iterations.

You may also want to consider counting up instead of down if you do this, if you goal is to exit early then generally speaking you will do better to start with the small numbers because the sum of more extremal divisors (one very high, one very low) is larger. Also with smaller numbers there will be a higher density of divisors.

Note that my code is not exactly correct, there are some edge cases to consider, perfect squares are one example.

I would think the improvement is O(N) -O(SQRT(N)). Counting up is a very good point. +1 — EvilTeach, Jun 25 '16 at 16:27
@EvilTeach the old algo is N, the new one is sqrtN, so iit's a factor of sqrtN better. I divided instead of subtracted. — Nir Friedman, Jun 25 '16 at 16:32
How about perfect squares though, sqrt(number) shouldn't be counted twice in that case should it? — harold, Jun 25 '16 at 16:36
That's why he wrote the last sentence I think ;). I got it figured out, thank you! — Fl.pf., Jun 25 '16 at 16:48

score 1 · Answer 2 · edited May 23 '17 at 12:33

1

If you really want to schrink the time of this loop and test big numbers, first you can try Miller-Rabin test to eliminate prime numbers. Then use Fermat factorisation method to find number's divisors.

If You test small numbers, You should iterate from 1 and test numbers only until the square root of the number (reference).

edited May 23 '17 at 12:33

Community

1
1

answered Jun 25 '16 at 16:13

R. Zagórski

20,020
5
65
90

Qumeric · Answer 3 · 2016-06-25T16:45:10.470

You can implement some simple optimizations:

Check only prime numbers. You can find them fast and pretty efficient with a simple sieve. Also you can find them once and save in a file. UPD: Be careful, it is easy to introduce a bug in such implementation. One possible way to do it right is to find all divisors, save them in array and then iterate through all possible combinations to calculate an actual sum. It can be done recursively.
Start from 2 and go up to the square root of the number and if you have found a divisor do sum += i + number/i. Natural order instead of reverse would be generally faster because it would instantly find small divisors which will increase the sum significantly.

If you are solving this problem for very large numbers you cannot do it really fast because it's an instance of Integer factorization problem which is known to be very hard to solve efficiently (i.e there are no known polynomial algorithm). So there are no way to make this loop much faster (asymptotically) than proposed implementation.

But on the other hand integer factorization is an old and very important problem so there are libraries which solve it incredebly fast with advanced heuristics and assembler-level optimizations.

`28=1+2+4+7+14` would not be found if you only check prime numbers. — Igor Tandetnik, Jun 25 '16 at 16:26
It would if you would check them in a loop properly. Sorry, I should have meant it. I'll update my answer. — Qumeric, Jun 25 '16 at 16:28

score 0 · Answer 4 · answered Jun 25 '16 at 16:39

There are some ways to optimize that.

loop sqrt(N) times, not N/2 times. (O(sqrt(N))
use pregenerated array. (O(0)?)
use the magical power of threads. (Depends)
use a sieve to eliminate primes. (O(N) ~ O(N^2))

Making a loop faster

4 Answers4