Reason for comparing longer is slower than comparing doubles

Question

I wrote a small program to calculate the first 18 triples (x,y,z) with x<y<z that satisfy x^3+y^3=z^3+1 .

During the game, to optimize the overall execution time, I found that using double for cubic values ​​and two sides of the equation is faster than using long . On my car, the difference is about 3 seconds.

Now I wonder why that is. I suppose this is somewhere in the internal processing of long , while comparing the two long Variables, since this is the only thing that changes in the calculation loops.

Here is my code:

 class Threes { public static void main(String[] args) { System.out.println("Threes --- Java"); int Z_MAX = 60000, Y_MAX = Z_MAX-1, X_MAX = Y_MAX-1; double[] powers = new double[Z_MAX+1]; for (int i = 0; i <= Z_MAX; i++) { powers[i] = Math.pow(i, 3); } System.out.println("Powers calculated"); int x, y, z; double right, left; int[][] sets = new int[18][3]; int foundCount = 0; long loopCount = 0; long start, end; start = System.currentTimeMillis(); for (x = 1 ; x < X_MAX; x++) { for (y = x + 1; y < Y_MAX; y++) { right = powers[x] + powers[y]; for (z = y + 1; z < Z_MAX; z++) { left = powers[z] + 1; if (right < left) { z = Z_MAX; } else if (right == left) { sets[foundCount][0] = x; sets[foundCount][1] = y; sets[foundCount][2] = z; foundCount++; end = System.currentTimeMillis(); System.out.println("found " + foundCount + ". set:\t" + x + "\t" + y + "\t" + z + "\t" + ((end - start) / 1000.0)); if (foundCount == 18) { x = X_MAX; y = Y_MAX; z = Z_MAX; } } loopCount++; } } } System.out.println("finished: " + loopCount); } } 

I changed the following lines:

 double[] powers = new double[Z_MAX+1]; 

becomes

 long[] powers = new long[Z_MAX+1]; 

and

 powers[i] = Math.pow(i, 3); 

becomes

 powers[i] = (long)Math.pow(i, 3); 

and

 double right, left; 

becomes

 long right, left; 

---

Bonus Question: What other possibilities do I have for optimizing the entire code in terms of the total duration of work? I know that to leave loopCount me a few milliseconds. I am sure that I need to significantly reduce the number of loop iterations. But how?

Answer 1

If you use a 32-bit operating system, performance for a long variable may be worse because it is a long 64-bit type. For example, with a 64-bit OS, Java can only compare with one machine instruction, but in a 32-bit environment, it must use several machine instructions, because at that time it can only process 32-bit instructions.

But for double this is not necessary, because 32-bit systems have machine instructions for 64-bit floating point numbers, even if they do not have them for 64-bit integers.

Also with the code:

 powers[i] = (long)Math.pow(i, 3); 

there are two unnecessary conversions, the first self (an integer) is converted to double (what Math.pow takes), and then the return value is converted back to a 64-bit integer (long).

Answer 2

It may be fair to say that your code spends most of its time in this section:

 for (z = y + 1; z < Z_MAX; z++) { left = powers[z] + 1; if (right < left) { z = Z_MAX; } 

And most of the time he will always take the same branch from the conditional. Therefore, as soon as your code reaches a steady state (i.e., after the processor branch predictor is configured), the execution time will be determined by the calculation itself: dependencies are minimized, so the latency of the command pipeline does not matter.

On a 32-bit machine, adding and comparing on 64-bit integer types requires more instructions than the equivalent on double s. Calculating a double will require more cycles, but that doesn't matter. We are dominated by bandwidth, not latency. Thus, the total execution time will be longer.

For further optimization, you can move +1 in the inner loop by evaluating right = powers[x] + powers[y] - 1 . But perhaps the optimizer already noticed this.

Answer 3

Your biggest “bonus” optimization will be to replace the z cycle with a calculation, for example:

 z = Math.round(Math.pow(left - 1, 1./3)); 

and check if z > y && left == powers[(int)z] + 1 .

Other improvements if you want to find all triples within your limits:

• start x at 2 instead of 1
• replace z = Z_MAX; on break; to exit the loop earlier
• calculate X_MAX as Math.pow((powers[Z_MAX] + 1)/2, 1./3) ~ = Z_MAX * Math.pow(0.5, 1./3) , since if x greater than z will exceed Z_MAX
• recalculate Y_MAX for each x as Math.pow(powers[Z_MAX] - powers[x] + 1, 1./3)/2

BTW, the more common way of arranging triples will use z as the main sort key, which can lead to a different first 18 than you get x ordering first. To change this, you will make your outer loop iterate over z, which would be easier anyway:

 for (z = 1; z < Z_MAX; z++) { for (y = 1; y < z - 1; y++) { zy = powers[z] - 1 - powers[y]; x = Math.round(Math.pow(zy, 1./3)); if (x < y && zy == powers[(int)x]) ...report triple found; } }