1

I am writing a program that looks for a solution of a diophantine equation. The program is cycling

for (int d = 0; d <= max; d++) {
    for (int c = 0; c < d; c++) {
        boolean possibleSolution = true;  
        possibleSolution =test1(c,d);
        if(possibleSolution) {possibleSolution =test2(c,d);}
        ...
        if(possibleSolution) {possibleSolution =test30(c,d);}
        if(possibleSolution) solutionFound(c,d);
    }
}

My testN methods are reasonably optimized. Most solutions are removed by a simple test1, but program has to run 30 pointless if(possibleSolution) checks. Is there a way to directly go to a new cycle of the testN yields false. Can a try ... catch block or some similar structure be adopted for this purposes?

  • Can't you just use the short-circuiting operator? if (test1(c,d) && test2(c,d) && ... && test30(c,d)) solutionFound(c,d) – Frank Jul 8 '16 at 15:05
  • Good point. I will. – sixtytrees Jul 8 '16 at 15:45
1

Based on your question break; will NOT work for you. You want to skip all further steps in this cycle, do c++ and go for a new round. This is done using continue. Break will end inner cycle do d++ and start inner cycle from 0.

  • Great point! I was having trouble with breaks. It seems like continue is a way to go. – sixtytrees Jul 9 '16 at 1:03
  • 1
    In this case - yes. Also, StackOverflow is better suited for technical questions like this one... – Poh Janish Jul 9 '16 at 1:04
  • Great "answer", pointing out a possible bug nowhere mentioned in the question and how to get around out. Great as well for giving an "answer" that is only applicable for code running inside a loop, and then only in specific cases. – gnasher729 Jul 9 '16 at 11:30
  • @gnasher729 break and continue do similar things. Having said that my if(chk) chk = nthTest() is equivalent to continue, not break, because the latter breaks out of the loop, not proceed to a new value in the loop. Now, your answer is useful, so I will browse your posts and upvote them. – sixtytrees Jul 9 '16 at 19:01
5

Measure first instead of making assumptions.

The sequence of 30 tests "if (possibleSolution)" is something that a good compiler should be able to optimise away. At the first "if (possibleSolution)" a good compiler would generate code that doesn't only skip one call, but figures out immediately that the second, third, and so on if are also going to fail, so it would generate code that jumps right past the call to solutionFound ().

An ugly but effective way of doing this by hand is using good old goto if your language / coding standards support it.

if (! test1 (c, d)) goto nosolution;
if (! test2 (c, d)) goto nosolution;
...
if (! test30 (c, d)) goto nosolution;
solutionfound (c, d);
nosolution: ;

An almost equally ugly way avoiding goto is this:

do {
    if (! test1 (c, d)) break;
    if (! test2 (c, d)) break;
    ...
    if (! test30 (c, d)) break;
    solutionfound (c, d);
} while (0);

But to make it fast, you want to minimise the total running time of all the test you are doing. To do this, measure for each test how long it runs, and how much the probability is that it is decisive, that is it determines there is no solution. Then you sort the test, doing the one with the smallest ratio of execution time divided by probability that the test decides the outcome. If one test takes 5 microseconds and has a 10% chance of failing, and another takes 7 microseconds with a 20% chance of failing, we do the second one first. (This has little effect if it is highly likely that all 30 tests pass).

This gets more complicated if the tests are not independent.

  • I am going through these steps now. I am sorting tests based on fractionOfSolutionsRemoved/(timeToRunTheTest). Once I am done I might post it on CodeReview. – sixtytrees Jul 8 '16 at 16:46
2

Replace

 If(pass) pass=testN(c,d);

With

  If(!testN(c,d)) {break;}

This way you get to a new cycle right away.

1

I'm not sure if this is what you mean, but you can do such a thing with a labeled break/continue (http://docs.oracle.com/javase/tutorial/java/nutsandbolts/branch.html):

main: for (int d = 0; d <= max; d++) {
    subMain: for (int c = 0; c < d; c++) {
        boolean possibleSolution = test1(c,d);
        if(!possibleSolution)
            continue main;
        possibleSolution = test2(c,d);
        ...
        if(possibleSolution)
            break main;
        else continue subMain;
        ...etc.
    }
}
1

You could use java 8's Streams, which will do short-circuiting under the hood for you.

To get around some boxing/unboxing you can define this internal interface :

private interface SolutionTest {
    boolean test(int a, int b);
}

With this in place you can introduce these helper methods :

private boolean isPossibleSolution(int c, int d) {
    return allTests().anyMatch(solutionTest -> solutionTest.test(c, d));
}

private Stream<SolutionTest> allTests() {
    return Stream.of(
                this::test1,
                this::test2,
                //...

                this::test30
        );
}

Which will allow the main code to be as simple as :

IntStream.rangeClosed(0, max)
        .forEach(d -> IntStream.range(0, d)
                .filter(c -> isPossibleSolution(c, d))
                .findFirst()
                .ifPresent(c -> solutionFound(c, d)));

anyMatch() and findFirst() are the methods that do all the short circuiting for you. And as a bonus it's all a lot less verbose, and way more readable.

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.