Optimizing a nested loop in C

Question

I have a nested loop to find all possible combinations of numbers between 1 and x in groups of 4, where a < b < c < d.

A method is called as each group is discovered to do a simple equivalency test on the sum of those numbers.

The loop does work and produces expected output (1 set of numbers for this particular x), however it takes 12+ seconds to find this answer and another ~5 to test the remaining possibilities, which is definitely bad, considering the x values are < 1000.

I tried having the outer loop iterate a < x - 3 times, the b loop b < x - 2 times, down to d < x times which didn't make a noticeable difference.

What would be a better approach in changing this loop?

for (a = 1; a < x; a++) {
    for (b = a + 1; b < x; b++) {
        for (c = b + 1; c < x; c++) {
            for (d = c + 1; d < x; d++) {
                check(a, b, c, d);
            }
        }
    }
}

How many combinations do you think you are checking? How much time do you think is a reasonable amount of time for each combination check to take? — David Schwartz
– David Schwartz, Commented Jan 9, 2017 at 5:07
Are you just trying to calculate the sum of every set of four numbers? I think it might help if you explained a bit more about what you're trying to do here. I would imagine most of the optimization opportunities lie in the check() function, which you haven't revealed here. — r3mainer
– r3mainer, Commented Jan 9, 2017 at 5:20
The entire loop should run in under a second. As for combinations I have put a print statement in the loop and I believe i'm getting the correct number with any given x. I can add the method code if necessary but it's checking whether a+b+c+d && a * b * c * d == x, and printing those numbers if true. — user6824588
– user6824588, Commented Jan 9, 2017 at 5:25
You want this to run in under a second? If x is 1000, then the inner loop will iterate (999 choose 4) times, which is over 41 billion unless I'm mistaken. You're going to need a very fast processor to do that. — r3mainer
– r3mainer, Commented Jan 9, 2017 at 5:33
If you want your computation to run in less than 1 second then in all likelihood you need an approach altogether different from enumerating and testing every possible combination. — John Bollinger
– John Bollinger, Commented Jan 9, 2017 at 5:57

Oak · Accepted Answer · 2017-01-11 14:42:59Z

2

With such a deep level of nesting, any early exit you can introduce - particularly at the outer loops - could net big gains.

For example, you write that check is testing a + b + c + d == x && a * b * c * d == x - so you can compute the intermediate sum and product, and break when you encounter numbers that would make any selection of later numbers impossible.

An example:

for (a = 1; a < x; a++) {
  for (b = a + 1; b < x; b++) {
    int sumAB = a + b;
    if (sumAB + sumAB > x) break;
    int prodAB = a * b;
    if (prodAB * prodAB > x) break;
    for (c = b + 1; c < x; c++) {
      int sumABC = sumAB + c;
      if (sumABC + c > x) break;
      int prodABC = prodAB * c;
      if (prodABC * c > x) break;
      for (d = c + 1; d < x; d++) {
        int sumABCD = sumABC + d;
        if (sumABCD > x) break;
        if (sumABCD != x) continue;
        int prodABCD = prodABC * d;
        if (prodABCD > x) break;
        if (prodABCD != x) continue;
        printf("%d, %d, %d, %d\n", a, b, c, d);
      }
    }
  }
}

This is just an example - you can constrain all the checks here further (e.g. make the first check be sumAB + sumAB + 3 > x). The point is to focus on early exits.

I added a counter for each loop, counting how many times it was entered, and tried your version and my version, with x = 100. My version has orders of magnitude less loop entries:

No early exits: 99, 4851, 156849, 3764376
With early exits: 99, 4851, 1122, 848

edited Jan 11, 2017 at 14:42

answered Jan 11, 2017 at 13:35

Oak

27.1k8 gold badges103 silver badges160 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Peter - Reinstate Monica Over a year ago

Actually, 6 or 7 orders of magnitude.

Peter - Reinstate Monica Over a year ago

Btw, you should not continue but break if one of the conditions is met because all subsequent sums and products generated in that branch will be larger than the partial sum or product, so that the branch can be pruned right there. That runs a million times faster. The beauty is that the pruning's benefits will grow with x (i.e. when they are needed most) because almost all combinations are too large.

Oak Over a year ago

@Stargateur do you know for which x it's supposed to show a result? I don't, which indeed makes it difficult to test. The problem is similar to perfect numbers but not identical, and I couldn't find any reference online of possible answers.

Oak Over a year ago

@PeterA.Schneider Whoops of course you are right, fixed. Required being a bit more verbose in the innermost loop.

Peter - Reinstate Monica Over a year ago

You inlined the check() :-).

|

Collectives™ on Stack Overflow

Optimizing a nested loop in C

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related