CODEWITHSUNDEEP
cperformancefor-loop
Coffee Maker
Coffee Maker

Reputation: 1573

How do I optimize these C for loops?

I chose to do these Project Euler problems in C because I was under the impression that C is fast, but that doesn't seem to be the case. Both of the following loops are extremely slow:

int problem_7 () { 
  int n = 0;
  for (int i = 1; i <= 10001; i++) {
      for (int j = (i==1)?1:n+1; j > 0; j++) {
          int factorCounter = 0;
          for (int k = 1; k <= j/2; k++)
              factorCounter += (j % k == 0);
          if (factorCounter == 1) {
              n = j;
              break;
          }
      }
  }
  return n;
}


long long int problem_10 () {
  long long int sum = 0;
  for (int i = 2; i < 2000000; i++) {
      int factorCount = 0;
      for (int j = 1; j <= i/2; j++) {
          factorCount += (i % j == 0);
          sum += i*(j == i/2 && factorCount == 1);
      }
  }

  return sum; 
}

Is there any way I can make these loops run faster? They do what they're supposed to do, but they each take like 5 minutes to execute.

Upvotes: 0

Views: 219

Answers (4)

Glenn Teitelbaum
Glenn Teitelbaum

Reputation: 10343

With branch prediction using boolean numeric values is not as needed:

Looking at problem7 for example, this can be sped up by using if statements:

  int n = 0;
  for (int i = 1; i <= 10001; i++) {
      for (int j = (i==1)?1:n+1; j > 0; j++) {
          int factorCounter = 0;
          for (int k = 1; k <= j/2; k++)
          {
              if (j%k==0)                 // code is changed HERE
              {
                factorCounter ++;
                if (factorCounter > 1)
                {
                      break;
                }
              }                          // code change ends here
          }
          if (factorCounter == 1) {
              n = j;
              break;
          }
      }

This completes in 0.88secs as opposed to the original's 9.5secs -- over 10 times faster from that one change

Explanation of optimization and rational for equivalence:

The change made was from the original line:

factorCounter += (j % k == 0);

First change that to its equivalent:

if (j%k==0)
{
    factorCounter ++;
}

Notice how factorCounter can only increment, and after the loop any value over 1 is discarded because (factorCounter == 1) will be false, so once it is greater than 1, there is no reason to continue the loop. Also notice that the value of factorCounter can only be changed when (j%k==0) so the test for factorCounter > 1 should occur inside the if check, the code is now:

if (j%k==0)
{
      factorCounter ++;
      if (factorCounter > 1)
      {
         break;   // We stop the loop much earlier HERE
      }
}

And exiting the loop early is what gives the performance gain

Upvotes: 2

user904963
user904963

Reputation: 1583

A more direct approach to the problem executes almost immediately. You don't really need that many optimizations.

#include <iostream>
#include <cmath>

using namespace std;

bool isPrime(int j)
{
    for(int fac = 2; fac < sqrt(j)+0.5; ++fac)
        if(j%fac == 0)
            return false;

    return true;
}

int main()
{
    int primesFound = 1; // 2 is prime
    int possiblePrime = 1;

    while(primesFound != 10001)
    {
        possiblePrime += 2;
        if(isPrime(possiblePrime))
            ++primesFound;
    }

    cout << possiblePrime << endl;
}

Upvotes: 1

1337 on Tuesdays
1337 on Tuesdays

Reputation: 154

C is fast. Higher level languages can be fast as well. But even the best compiler can't optimize out the extra operations you're having it do! A simple way to reduce number of operations in your problem 7 algorithm would be to break the deepest for loop if factorCounter becomes greater than 1. Sorry to break it to you but: it's not the compiler it's the algorithm!

Upvotes: 1

David Titarenco
David Titarenco

Reputation: 33406

I guess I'll make this an answer. Your program is slow because your loops are poorly designed and poorly nested. I'm not going to do a complexity analysis, but you're somewhere in the range of O(N^x) where x > 4 (from what I can tell).

It's just bad programming and it has little to do with loop optimization. You need to use something like the Sieve of Eratosthenes to solve Euler 7. I won't give you the solution here, as with the Wiki article it's fairly trivial to solve.

Upvotes: 1

Related Questions