CODEWITHSUNDEEP
c++loopsoptimization
Fl.pf.
Fl.pf.

Reputation: 345

Making a loop faster

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?)

Upvotes: 1

Views: 508

Answers (4)

Qumeric
Qumeric

Reputation: 518

You can implement some simple optimizations:

  1. 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.
  2. 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.

Upvotes: 0

user5058091
user5058091

Reputation:

There are some ways to optimize that.

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

Upvotes: 0

R. Zag&#243;rski
R. Zag&#243;rski

Reputation: 20268

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).

Upvotes: 1

Nir Friedman
Nir Friedman

Reputation: 17714

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.

Upvotes: 4

Related Questions