JNI calls are known to be slow...

Here are my tests thus far in Java with a faster sqrt function.  The last one is almost twice as fast.  However, they're not working on one of my layouts (except the second one, which is slower).  The layout works fine with Math.sqrt(), so I guess they're not accurate enough for that particular layout, which is the main one I'm trying to speed up.  They may be of use to other users though.. they're more accurate and faster than other methods I've seen.  I'll keep playing.

1. long timer = 0;
2. int looptest = 1000000;
3. float d;
4. void setup() {
5.   size(500, 500);
6. }
7. void draw() {
8.   timer = System.nanoTime();
9.   for (int i = 0; i < looptest; i++) {
10.     d = myDist1();
11.   }
12.   println("Sqrt1:\t" + d + "\t\t" +(System.nanoTime()-timer));
13.   timer = System.nanoTime();
14.   for (int i = 0; i < looptest; i++) {
15.     d = myDist2();
16.   }
17.   println("Sqrt2:\t" + d + "\t\t" +(System.nanoTime()-timer));
18.   timer = System.nanoTime();
19.   for (int i = 0; i < looptest; i++) {
20.     d = myDist3();
21.   }
22.   println("Sqrt3:\t" + d + "\t\t" +(System.nanoTime()-timer));
23.   timer = System.nanoTime();
24.   for (int i = 0; i < looptest; i++) {
25.     d = myDist4();
26.   }
27.   println("Sqrt4:\t" + d + "\t\t" +(System.nanoTime()-timer));
28.   timer = System.nanoTime();
29.   for (int i = 0; i < looptest; i++) {
30.     d = myDist5();
31.   }
32.   println("Sqrt5:\t" + d + "\t\t" +(System.nanoTime()-timer));
33.   timer = System.nanoTime();
34.   for (int i = 0; i < looptest; i++) {
35.     d = myDist6();
36.   }
37.   println("Sqrt6:\t" + d + "\t\t" +(System.nanoTime()-timer));
38.  
39.    timer = System.nanoTime();
40.   for (int i = 0; i < looptest; i++) {
41.     d = myDist7();
42.   }
43.   println("Sqrt7:\t" + d + "\t\t" +(System.nanoTime()-timer));
44.   println("");
45. }
46. float myDist1() {
47.   //Equal to PApplet sqrt
48.   return (float)Math.sqrt((mouseX - 0) * (mouseX - 0) + (mouseY - 0) * (mouseY - 0));
49. }
50. float myDist2() {
51.   return Sqrt2((mouseX - 0) * (mouseX - 0) + (mouseY - 0) * (mouseY - 0));
52. }
53. float myDist3() {
54.   return Sqrt3((mouseX - 0) * (mouseX - 0) + (mouseY - 0) * (mouseY - 0));
55. }
56. float myDist4() {
57.   return Sqrt4((mouseX - 0) * (mouseX - 0) + (mouseY - 0) * (mouseY - 0));
58. }
59. float myDist5() {
60.   return Sqrt5((mouseX - 0) * (mouseX - 0) + (mouseY - 0) * (mouseY - 0));
61. }
62. float myDist6() {
63.   return Sqrt6((mouseX - 0) * (mouseX - 0) + (mouseY - 0) * (mouseY - 0));
64. }
65. float myDist7() {
66.   return Sqrt7((mouseX - 0) * (mouseX - 0) + (mouseY - 0) * (mouseY - 0));
67. }
68. static float Sqrt2(float x) {
69.   float xhalf = 0.5f*x;
70.   int i = Float.floatToIntBits(x); // get bits for floating value
71.   i = 0x5f375a86- (i>>1); // gives initial guess y0
72.   float ix = Float.intBitsToFloat(i); // convert bits back to float
73.   x = x*ix*(1.5f-xhalf*ix*ix); // Newton step, repeating increases accuracy
74.   return x;
75. }
76. public static float Sqrt3(float x) {
77.   int i = Float.floatToIntBits(x);
78.   // adjust bias
79.   i  += 127 << 23;
80.   // approximation of square root
81.   i >>= 1;
82.   return -Float.intBitsToFloat(i);
83. }
84. public static float Sqrt4(float x) {
85.   int i = Float.floatToIntBits(x);
86.   // adjust bias
87.   i  += 1065353216;
88.   // approximation of square root
89.   i >>= 1;
90.   return -Float.intBitsToFloat(i);
91. }
92. public static float Sqrt5(float x) 
93. {
94.   int i = Float.floatToIntBits(x);
95.   i = (1<<29) + (i >> 1) - (1<<22);
96.   return Float.intBitsToFloat(i);
97. } 
98. public static float Sqrt6(float x) {
99.   int i = Float.floatToIntBits(x);
100.   i = 532676608 + (i >> 1);
101.   return Float.intBitsToFloat(i);
102. }
103. public static float Sqrt7(float x) {
104.   int i = Float.floatToRawIntBits(x);
105.   i = 532676608 + (i >> 1);
106.   return Float.intBitsToFloat(i);
107. }

as far as i understand this:
http://www.massapi.com/source/jdk1.6.0_17/src/java/lang/StrictMath.java.html
java also makes use of JNI to use Math-funcions.
if i'm wrong here, maybe someone could explain how this is done?!?

searching for "fdlibm" gave me this: http://www.netlib.org/fdlibm/

so this: http://www.netlib.org/fdlibm/e_sqrt.c might be the actualy sqrt function that java uses.

you could give it a try and test if its slower when you implement this yourself in comparision with javas Match.sqrt().
if is it is, it might be worth the effort to write some C-code and make JNI-calls.

What about a GLSL shader that runs on the GPU?  Video cards often have high performance sqrt functions.  Might something be written that sends a variable to the shader, which then returns the sqrt?

I have the functions to load GLSL code, just not sure what to write in the shader to get the return.

Yes, on second thought, I wanted to add that it can be worth trying to test the JNI call: perhaps the FPU computation can be so much faster than the JNI overhead is worth it. Like all optimizations, they must be tested!
Preferably with a framework like Caliper, which takes in account JVM warmup and Jit kick-up after a number of iterations...

As I though, Java is indeed using JNI to do their math, although again it can be slow because of the foreign call (such call is worthwhile in an arraycopy operation, as it is long, perhaps less in a single sqrt one...). They do these calls, apparently, more for accuracy (using the same math, via FPU, than other softwares allows for reproducible results) than for speed...

If you go the JNI way, it might be worth processing a whole array of numbers at once, perhaps reducing the impact of the JNI call.

So far, in pure Java, this is performing the fastest with a close approximation.

1. public static float fastSqrt(float x) {
2.     return Float.intBitsToFloat(532483686 + (Float.floatToRawIntBits(x) >> 1));
3. }

So far, in pure Java, this is performing the fastest with a close approximation.

I tried this and got 0.5% to 1.5% error. So although fast it might not be accurate enough depending on the application.


You might consider Apache Commons Math 2.2, they claim their FastMath class is "Faster, more accurate, portable alternative to StrictMath ". As well as sqrt it has many other math functions.

Although I have not tested these claims I am using the FastMath class in a new library I am developing primarily for speed and portability.

Although the

Thanks for the info, I'll also add the FastMath to my project.  :)  Unfortunately, they're still using Math.sqrt() in that Class - so no performance boost there.  I'm using the sqrt for physics calculations and distance in a graph layout.  So for my purpose, the error was within an acceptable range.  I run it through 50 steps using the Fast Sqrt, then drop it down to Math.sqrt() for the last few iterations.

Unfortunately, they're still using Math.sqrt() in that Class - so no performance boost there

Sorry missed that

It is perhaps worth pointing out that a common optimization we used to make back in the day was to omit the use of square root altogether, particularly when checking distances in 2d or 3d space.

Thanks Jim, I have used that on several aspects of my code were a particular distance was not needed but as an aspect of collision detection.  Definitely worth pointing out. :-)