Why does the break function add extra processing time to for loops?

Question

I'm currently working my way through a book on simple optimizations. One of the algorithms shown was:

Print all solutions to a³ + b³ = c³ + d³ (where a, b, c, d are less than 1000)

(I went with 100 so it would run quicker on my slow netbook)

I programmed up their solution (Their solution and their first offered optimisation are included), however the break optimisation offered actually made the algorithm a fair bit slower.

public static void doUnoptimised() {
    for(int a = 1; a < 100; a++) 
    {
        for(int b = 1; b < 100; b++)
        {
            for(int c = 1; c < 100; c++)
            {
                for(int d = 1; d < 100; d++) {
                    if(Math.pow(a, 3) + Math.pow(b, 3) == Math.pow(c, 3) + Math.pow(d, 3))
                    {
                        System.out.println("A:" + a + " B:" + b + " C:" + c + " D:" + d);
                    }
                }
            }
        }
    }
}

public static void doFirstOptimised() {
    for(int a = 1; a < 100; a++) 
    {
        for(int b = 1; b < 100; b++)
        {
            for(int c = 1; c < 100; c++)
            {
                for(int d = 1; d < 100; d++) {
                    if(Math.pow(a, 3) + Math.pow(b, 3) == Math.pow(c, 3) + Math.pow(d, 3))
                    {
                        System.out.println("A:" + a + " B:" + b + " C:" + c + " D:" + d);
                        break;
                    }
                }
            }
        }
    }
}

Why is that? Note that this isn't my solution, this is the one shown in the book, and they go on with more optimizations later but I'm interested in why this optimization was such an epic fail.

Edit - Perhaps I'm not being clear enough here. I know this is a barely noticeable change and I understand why this is an improvement and have already gone through the better optimizations offered in the book. (Thanks for those giving better optimisations though, appreciate the effort) However this particular step one does not work at all and im trying to figure out why. But at this stage it seems like my jvm is just weird.

Answer 1

There is an assumption in this optimisation that there is only one possible d for any combination of a, b and c.

What the break; does is stop the inner loop and so once we have a solution, we can give up looking for another one and this saves work, thus reducing the time.

There is many, much better optimisation, however using a break; like this, or a return is a common optimisation used in less contrived situations.

For example, how might you implement ArrayList.indexOf naively ignoring null values.

public int indexOf(Object o) {
    int index = -1;
    for (int i = 0; i < size; i++)
        if (o.equals(elementData[i]))
            if (index == -1)
                index = i;
    return index;
}

Note: this has to scan every entry even if it is the first entry to be found. A faster way is to use break to say; stop iterating if I have a solution.

public int indexOf(Object o) {
    int index = -1;
    for (int i = 0; i < size; i++)
        if (o.equals(elementData[i]))
            index = i;
            break;
        }
    return index;
}

However, break is not needed here because the next thing it does is return

public int indexOf(Object o) {
    for (int i = 0; i < size; i++)
        if (o.equals(elementData[i]))
            return i;
    return -1;
}

taking into account null values, the actual implementation is

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}