Last active
October 20, 2017 07:03
-
-
Save myui/9ea4a9941932a7d942d6e7d5d6c619cf to your computer and use it in GitHub Desktop.
FastInverseSquareRootTest
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class FastInverseSquareRootTest { | |
private static FastInverseSquareRootTest conductTestHalfPrecision() { | |
float result = 0F; | |
long startTime, endTime, midTime; | |
startTime = System.nanoTime(); | |
for (float x = 1F; x < 4_000_000F; x += 0.25F) { | |
result += 1F / (float) Math.sqrt(x); | |
} | |
midTime = System.nanoTime(); | |
for (float x = 1F; x < 4_000_000F; x += 0.25F) { | |
result += fastInverseSquareRoot(x); | |
} | |
endTime = System.nanoTime(); | |
if (result == 0) | |
System.out.println("Wow!"); | |
return new FastInverseSquareRootTest(midTime - startTime, endTime - midTime); | |
} | |
private static FastInverseSquareRootTest conductTestDoublePrecision() { | |
double result = 0d; | |
long startTime, endTime, midTime; | |
startTime = System.nanoTime(); | |
for (double x = 1d; x < 4_000_000d; x += 0.25d) { | |
result += 1d / Math.sqrt(x); | |
} | |
midTime = System.nanoTime(); | |
for (double x = 1d; x < 4_000_000d; x += 0.25D) { | |
result += fastInverseSquareRoot(x); | |
} | |
endTime = System.nanoTime(); | |
if (result == 0) | |
System.out.println("Wow!"); | |
return new FastInverseSquareRootTest(midTime - startTime, endTime - midTime); | |
} | |
/** | |
* https://en.wikipedia.org/wiki/Fast_inverse_square_root | |
*/ | |
@Deprecated | |
private static float fastInverseSquareRoot(final float x) { | |
final float hx = 0.5f * x; | |
int i = 0x5f375a86 - (Float.floatToRawIntBits(x) >>> 1); | |
float y = Float.intBitsToFloat(i); | |
y *= (1.5f - hx * y * y); // pass 1 | |
y *= (1.5f - hx * y * y); // pass 2 | |
y *= (1.5f - hx * y * y); // pass 3 | |
//y *= (1.5f - hx * y * y); // pass 4 | |
// more pass for more accuracy | |
return y; | |
} | |
/** | |
* https://en.wikipedia.org/wiki/Fast_inverse_square_root | |
*/ | |
private static double fastInverseSquareRoot(final double x) { | |
final double hx = 0.5d * x; | |
long i = 0x5fe6eb50c7b537a9L - (Double.doubleToRawLongBits(x) >>> 1); | |
double y = Double.longBitsToDouble(i); | |
y *= (1.5d - hx * y * y); // pass 1 | |
y *= (1.5d - hx * y * y); // pass 2 | |
y *= (1.5d - hx * y * y); // pass 3 | |
y *= (1.5d - hx * y * y); // pass 4 | |
// more pass for more accuracy | |
return y; | |
} | |
public static void main(String[] args) throws Exception { | |
for (int i = 0; i < 7; i++) { | |
System.out.println("-- round #" + (i + 1)); | |
System.out.println("-- Half Precision"); | |
System.out.print(conductTestHalfPrecision().toString()); | |
System.out.println("-- Double Precision"); | |
System.out.println(conductTestDoublePrecision().toString()); | |
} | |
} | |
private long controlDiff; | |
private long experimentalDiff; | |
private double percentError; | |
public FastInverseSquareRootTest(long controlDiff, long experimentalDiff) { | |
this.experimentalDiff = experimentalDiff; | |
this.controlDiff = controlDiff; | |
this.percentError = 100D * (experimentalDiff - controlDiff) / controlDiff; | |
} | |
@Override | |
public String toString() { | |
StringBuilder sb = new StringBuilder(); | |
sb.append(String.format("1F / Math.sqrt() took %d nanoseconds.%n", controlDiff)); | |
sb.append( | |
String.format("Fast Inverse Square Root took %d nanoseconds.%n", experimentalDiff)); | |
sb.append( | |
String.format("Fast Inverse Square Root was %f percent %s than 1F / Math.sqrt()%n", | |
Math.abs(percentError), percentError > 0D ? "slower" : "faster")); | |
return sb.toString(); | |
} | |
} |
Changed to include the following line:
if (result == 0) System.out.println("Wow!");
-- Oracle JDK 1.8.0_131
round #1
1F / Math.sqrt() took 100785704 nanoseconds.
Fast Inverse Square Root took 54970357 nanoseconds.
Fast Inverse Square Root was 45.458180 percent faster than 1F / Math.sqrt()
round #2
1F / Math.sqrt() took 96160016 nanoseconds.
Fast Inverse Square Root took 44801597 nanoseconds.
Fast Inverse Square Root was 53.409329 percent faster than 1F / Math.sqrt()
round #3
1F / Math.sqrt() took 95342506 nanoseconds.
Fast Inverse Square Root took 66287985 nanoseconds.
Fast Inverse Square Root was 30.473838 percent faster than 1F / Math.sqrt()
round #4
1F / Math.sqrt() took 93024088 nanoseconds.
Fast Inverse Square Root took 64441946 nanoseconds.
Fast Inverse Square Root was 30.725528 percent faster than 1F / Math.sqrt()
round #5
1F / Math.sqrt() took 92984782 nanoseconds.
Fast Inverse Square Root took 68935498 nanoseconds.
Fast Inverse Square Root was 25.863677 percent faster than 1F / Math.sqrt()
round #6
1F / Math.sqrt() took 91463161 nanoseconds.
Fast Inverse Square Root took 65763758 nanoseconds.
Fast Inverse Square Root was 28.098092 percent faster than 1F / Math.sqrt()
round #7
1F / Math.sqrt() took 93614081 nanoseconds.
Fast Inverse Square Root took 77680510 nanoseconds.
Fast Inverse Square Root was 17.020485 percent faster than 1F / Math.sqrt()
-- Oracle JDK 1.7.0_80
round #1
1F / Math.sqrt() took 97080000 nanoseconds.
Fast Inverse Square Root took 68202000 nanoseconds.
Fast Inverse Square Root was 29.746601 percent faster than 1F / Math.sqrt()
round #2
1F / Math.sqrt() took 61638000 nanoseconds.
Fast Inverse Square Root took 55139000 nanoseconds.
Fast Inverse Square Root was 10.543820 percent faster than 1F / Math.sqrt()
round #3
1F / Math.sqrt() took 95171000 nanoseconds.
Fast Inverse Square Root took 67648000 nanoseconds.
Fast Inverse Square Root was 28.919524 percent faster than 1F / Math.sqrt()
round #4
1F / Math.sqrt() took 91658000 nanoseconds.
Fast Inverse Square Root took 68573000 nanoseconds.
Fast Inverse Square Root was 25.186018 percent faster than 1F / Math.sqrt()
round #5
1F / Math.sqrt() took 91981000 nanoseconds.
Fast Inverse Square Root took 66483000 nanoseconds.
Fast Inverse Square Root was 27.720942 percent faster than 1F / Math.sqrt()
round #6
1F / Math.sqrt() took 90172000 nanoseconds.
Fast Inverse Square Root took 68919000 nanoseconds.
Fast Inverse Square Root was 23.569401 percent faster than 1F / Math.sqrt()
round #7
1F / Math.sqrt() took 93429000 nanoseconds.
Fast Inverse Square Root took 68157000 nanoseconds.
Fast Inverse Square Root was 27.049417 percent faster than 1F / Math.sqrt()
-- Oracle JDK 1.8.0_131
-- round #1
-- Half Precision
1F / Math.sqrt() took 101042057 nanoseconds.
Fast Inverse Square Root took 63963925 nanoseconds.
Fast Inverse Square Root was 36.695741 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 85597454 nanoseconds.
Fast Inverse Square Root took 60539798 nanoseconds.
Fast Inverse Square Root was 29.273833 percent faster than 1F / Math.sqrt()
-- round #2
-- Half Precision
1F / Math.sqrt() took 43667759 nanoseconds.
Fast Inverse Square Root took 58064031 nanoseconds.
Fast Inverse Square Root was 32.967737 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 81324071 nanoseconds.
Fast Inverse Square Root took 42709862 nanoseconds.
Fast Inverse Square Root was 47.481894 percent faster than 1F / Math.sqrt()
-- round #3
-- Half Precision
1F / Math.sqrt() took 94499349 nanoseconds.
Fast Inverse Square Root took 68485975 nanoseconds.
Fast Inverse Square Root was 27.527570 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 207288032 nanoseconds.
Fast Inverse Square Root took 70063062 nanoseconds.
Fast Inverse Square Root was 66.200141 percent faster than 1F / Math.sqrt()
-- round #4
-- Half Precision
1F / Math.sqrt() took 97661127 nanoseconds.
Fast Inverse Square Root took 69652756 nanoseconds.
Fast Inverse Square Root was 28.679140 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 214805991 nanoseconds.
Fast Inverse Square Root took 75630540 nanoseconds.
Fast Inverse Square Root was 64.791233 percent faster than 1F / Math.sqrt()
-- round #5
-- Half Precision
1F / Math.sqrt() took 91276088 nanoseconds.
Fast Inverse Square Root took 72992390 nanoseconds.
Fast Inverse Square Root was 20.031202 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 215063767 nanoseconds.
Fast Inverse Square Root took 64343787 nanoseconds.
Fast Inverse Square Root was 70.081531 percent faster than 1F / Math.sqrt()
-- round #6
-- Half Precision
1F / Math.sqrt() took 90433026 nanoseconds.
Fast Inverse Square Root took 65508368 nanoseconds.
Fast Inverse Square Root was 27.561455 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 211665862 nanoseconds.
Fast Inverse Square Root took 64483607 nanoseconds.
Fast Inverse Square Root was 69.535188 percent faster than 1F / Math.sqrt()
-- round #7
-- Half Precision
1F / Math.sqrt() took 91424838 nanoseconds.
Fast Inverse Square Root took 65904053 nanoseconds.
Fast Inverse Square Root was 27.914498 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 210977619 nanoseconds.
Fast Inverse Square Root took 64676029 nanoseconds.
Fast Inverse Square Root was 69.344602 percent faster than 1F / Math.sqrt()
-- Oracle JDK 1.8.0_131
-- round #1
-- Half Precision
1F / Math.sqrt() took 119408362 nanoseconds.
Fast Inverse Square Root took 129243550 nanoseconds.
Fast Inverse Square Root was 8.236599 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 87271640 nanoseconds.
Fast Inverse Square Root took 50914515 nanoseconds.
Fast Inverse Square Root was 41.659725 percent faster than 1F / Math.sqrt()
-- round #2
-- Half Precision
1F / Math.sqrt() took 95817843 nanoseconds.
Fast Inverse Square Root took 44140483 nanoseconds.
Fast Inverse Square Root was 53.932919 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 82167246 nanoseconds.
Fast Inverse Square Root took 49448796 nanoseconds.
Fast Inverse Square Root was 39.819334 percent faster than 1F / Math.sqrt()
-- round #3
-- Half Precision
1F / Math.sqrt() took 105037065 nanoseconds.
Fast Inverse Square Root took 68954096 nanoseconds.
Fast Inverse Square Root was 34.352606 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 211833117 nanoseconds.
Fast Inverse Square Root took 83454723 nanoseconds.
Fast Inverse Square Root was 60.603552 percent faster than 1F / Math.sqrt()
-- round #4
-- Half Precision
1F / Math.sqrt() took 90029539 nanoseconds.
Fast Inverse Square Root took 62363589 nanoseconds.
Fast Inverse Square Root was 30.729859 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 209639641 nanoseconds.
Fast Inverse Square Root took 64658225 nanoseconds.
Fast Inverse Square Root was 69.157443 percent faster than 1F / Math.sqrt()
-- round #5
-- Half Precision
1F / Math.sqrt() took 86651734 nanoseconds.
Fast Inverse Square Root took 67692092 nanoseconds.
Fast Inverse Square Root was 21.880280 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 207212560 nanoseconds.
Fast Inverse Square Root took 63304760 nanoseconds.
Fast Inverse Square Root was 69.449362 percent faster than 1F / Math.sqrt()
-- round #6
-- Half Precision
1F / Math.sqrt() took 96142163 nanoseconds.
Fast Inverse Square Root took 66890555 nanoseconds.
Fast Inverse Square Root was 30.425369 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 206229592 nanoseconds.
Fast Inverse Square Root took 72511797 nanoseconds.
Fast Inverse Square Root was 64.839286 percent faster than 1F / Math.sqrt()
-- round #7
-- Half Precision
1F / Math.sqrt() took 96971587 nanoseconds.
Fast Inverse Square Root took 84098800 nanoseconds.
Fast Inverse Square Root was 13.274803 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 212272525 nanoseconds.
Fast Inverse Square Root took 72670830 nanoseconds.
Fast Inverse Square Root was 65.765315 percent faster than 1F / Math.sqrt()
Update code for accuracy improvement.
-- round #1
-- Half Precision
1F / Math.sqrt() took 96431851 nanoseconds.
Fast Inverse Square Root took 80547998 nanoseconds.
Fast Inverse Square Root was 16.471584 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 83565434 nanoseconds.
Fast Inverse Square Root took 110340981 nanoseconds.
Fast Inverse Square Root was 32.041414 percent slower than 1F / Math.sqrt()
-- round #2
-- Half Precision
1F / Math.sqrt() took 52002132 nanoseconds.
Fast Inverse Square Root took 79997783 nanoseconds.
Fast Inverse Square Root was 53.835583 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 78887528 nanoseconds.
Fast Inverse Square Root took 86736896 nanoseconds.
Fast Inverse Square Root was 9.950075 percent slower than 1F / Math.sqrt()
-- round #3
-- Half Precision
1F / Math.sqrt() took 95304733 nanoseconds.
Fast Inverse Square Root took 91379157 nanoseconds.
Fast Inverse Square Root was 4.118973 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 214882717 nanoseconds.
Fast Inverse Square Root took 84281199 nanoseconds.
Fast Inverse Square Root was 60.778047 percent faster than 1F / Math.sqrt()
-- round #4
-- Half Precision
1F / Math.sqrt() took 88122956 nanoseconds.
Fast Inverse Square Root took 86203440 nanoseconds.
Fast Inverse Square Root was 2.178225 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 247621658 nanoseconds.
Fast Inverse Square Root took 90271870 nanoseconds.
Fast Inverse Square Root was 63.544437 percent faster than 1F / Math.sqrt()
-- round #5
-- Half Precision
1F / Math.sqrt() took 98780695 nanoseconds.
Fast Inverse Square Root took 98198585 nanoseconds.
Fast Inverse Square Root was 0.589295 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 230090824 nanoseconds.
Fast Inverse Square Root took 100153887 nanoseconds.
Fast Inverse Square Root was 56.472020 percent faster than 1F / Math.sqrt()
-- round #6
-- Half Precision
1F / Math.sqrt() took 102106989 nanoseconds.
Fast Inverse Square Root took 77352075 nanoseconds.
Fast Inverse Square Root was 24.244094 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 213574741 nanoseconds.
Fast Inverse Square Root took 89301493 nanoseconds.
Fast Inverse Square Root was 58.187240 percent faster than 1F / Math.sqrt()
-- round #7
-- Half Precision
1F / Math.sqrt() took 99180027 nanoseconds.
Fast Inverse Square Root took 87742035 nanoseconds.
Fast Inverse Square Root was 11.532556 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 225609034 nanoseconds.
Fast Inverse Square Root took 99131834 nanoseconds.
Fast Inverse Square Root was 56.060344 percent faster than 1F / Math.sqrt()
changed result = fastInverseSquareRoot(x);
=> result += fastInverseSquareRoot(x);
4 passes
-- round #1
-- Half Precision
1F / Math.sqrt() took 99960196 nanoseconds.
Fast Inverse Square Root took 86346653 nanoseconds.
Fast Inverse Square Root was 13.618964 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 90733885 nanoseconds.
Fast Inverse Square Root took 120724513 nanoseconds.
Fast Inverse Square Root was 33.053393 percent slower than 1F / Math.sqrt()
-- round #2
-- Half Precision
1F / Math.sqrt() took 41279530 nanoseconds.
Fast Inverse Square Root took 83000631 nanoseconds.
Fast Inverse Square Root was 101.069709 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 84380185 nanoseconds.
Fast Inverse Square Root took 113285465 nanoseconds.
Fast Inverse Square Root was 34.256005 percent slower than 1F / Math.sqrt()
-- round #3
-- Half Precision
1F / Math.sqrt() took 49830862 nanoseconds.
Fast Inverse Square Root took 100835602 nanoseconds.
Fast Inverse Square Root was 102.355725 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 88810795 nanoseconds.
Fast Inverse Square Root took 106624545 nanoseconds.
Fast Inverse Square Root was 20.058091 percent slower than 1F / Math.sqrt()
-- round #4
-- Half Precision
1F / Math.sqrt() took 42146939 nanoseconds.
Fast Inverse Square Root took 83257436 nanoseconds.
Fast Inverse Square Root was 97.540884 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 80799409 nanoseconds.
Fast Inverse Square Root took 104173512 nanoseconds.
Fast Inverse Square Root was 28.928557 percent slower than 1F / Math.sqrt()
-- round #5
-- Half Precision
1F / Math.sqrt() took 49676249 nanoseconds.
Fast Inverse Square Root took 100314852 nanoseconds.
Fast Inverse Square Root was 101.937252 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 82046427 nanoseconds.
Fast Inverse Square Root took 101554961 nanoseconds.
Fast Inverse Square Root was 23.777433 percent slower than 1F / Math.sqrt()
-- round #6
-- Half Precision
1F / Math.sqrt() took 44570776 nanoseconds.
Fast Inverse Square Root took 85005375 nanoseconds.
Fast Inverse Square Root was 90.719980 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 81098272 nanoseconds.
Fast Inverse Square Root took 100395279 nanoseconds.
Fast Inverse Square Root was 23.794597 percent slower than 1F / Math.sqrt()
-- round #7
-- Half Precision
1F / Math.sqrt() took 45522212 nanoseconds.
Fast Inverse Square Root took 85772424 nanoseconds.
Fast Inverse Square Root was 88.418840 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 76633786 nanoseconds.
Fast Inverse Square Root took 137817873 nanoseconds.
Fast Inverse Square Root was 79.839572 percent slower than 1F / Math.sqrt()
2 passes
-- round #1
-- Half Precision
1F / Math.sqrt() took 101149329 nanoseconds.
Fast Inverse Square Root took 113856556 nanoseconds.
Fast Inverse Square Root was 12.562839 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 93899374 nanoseconds.
Fast Inverse Square Root took 89806362 nanoseconds.
Fast Inverse Square Root was 4.358934 percent faster than 1F / Math.sqrt()
-- round #2
-- Half Precision
1F / Math.sqrt() took 104581399 nanoseconds.
Fast Inverse Square Root took 69646875 nanoseconds.
Fast Inverse Square Root was 33.404147 percent faster than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 84388323 nanoseconds.
Fast Inverse Square Root took 68669101 nanoseconds.
Fast Inverse Square Root was 18.627248 percent faster than 1F / Math.sqrt()
-- round #3
-- Half Precision
1F / Math.sqrt() took 44317767 nanoseconds.
Fast Inverse Square Root took 89852883 nanoseconds.
Fast Inverse Square Root was 102.746864 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 92703915 nanoseconds.
Fast Inverse Square Root took 70705169 nanoseconds.
Fast Inverse Square Root was 23.730115 percent faster than 1F / Math.sqrt()
-- round #4
-- Half Precision
1F / Math.sqrt() took 44631338 nanoseconds.
Fast Inverse Square Root took 78310238 nanoseconds.
Fast Inverse Square Root was 75.460207 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 78062997 nanoseconds.
Fast Inverse Square Root took 74053872 nanoseconds.
Fast Inverse Square Root was 5.135756 percent faster than 1F / Math.sqrt()
-- round #5
-- Half Precision
1F / Math.sqrt() took 42400321 nanoseconds.
Fast Inverse Square Root took 74759019 nanoseconds.
Fast Inverse Square Root was 76.317106 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 88259638 nanoseconds.
Fast Inverse Square Root took 77499899 nanoseconds.
Fast Inverse Square Root was 12.191007 percent faster than 1F / Math.sqrt()
-- round #6
-- Half Precision
1F / Math.sqrt() took 50611586 nanoseconds.
Fast Inverse Square Root took 78417197 nanoseconds.
Fast Inverse Square Root was 54.939221 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 85775518 nanoseconds.
Fast Inverse Square Root took 74176179 nanoseconds.
Fast Inverse Square Root was 13.522902 percent faster than 1F / Math.sqrt()
-- round #7
-- Half Precision
1F / Math.sqrt() took 54423990 nanoseconds.
Fast Inverse Square Root took 69340036 nanoseconds.
Fast Inverse Square Root was 27.407116 percent slower than 1F / Math.sqrt()
-- Double Precision
1F / Math.sqrt() took 98538328 nanoseconds.
Fast Inverse Square Root took 77449707 nanoseconds.
Fast Inverse Square Root was 21.401440 percent faster than 1F / Math.sqrt()
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
https://stackoverflow.com/questions/16551140/why-is-fast-inverse-square-root-so-odd-and-slow-on-java
https://en.wikipedia.org/wiki/Fast_inverse_square_root
https://stackoverflow.com/questions/825221/where-can-i-find-the-source-code-for-javas-square-root-function
Without
if (result == 0) System.out.println("Wow!");