til: jni - java native interface
author / December 29, 2024
5 min read •
tl;dr
I was today years old when I learned that the Math.sqrt method in Java's Math class is not implemented in Java.
I was doing the Leetcode problem 367. Valid Perfect Square. It is to find if a given number is a perfect square or not.
The problem seems simple if you intend (which I thought of initially) to use the sqrt method of Math class in the Java lang API.
But the description of the question prohibits any use of built-in functions. That was a bummer because I couldn't think of any other
approach to solve this.
And mind you, this is tagged as Easy, amongst Leecode's difficulty classification of Easy, Medium and Hard.
I went to see the Discussion section, and most of them talk about using Binary Search, about how they get TLE exceeded, and how the problem isn't so Easy.
At this point, I really wanted to see what the actual implementation of Math.sqrt looked like. Because that would be benchmark if not the most
efficiently written code to calculate the square root of a number in Java.
I then went to Math.sqrt to see
the implementation. The method calls another sqrt method in StrictMath with a comment
"Note that hardware sqrt instructions frequently can be directly used by JITs and should be much faster than doing Math.sqrt in software",
which I had never heard of earlier. In fact most of the commonly used methods
of Math class are delegated to this class like the Math.pow, Math.ceil, Math.floor Et al.
The code in StrictMath in turn is just a method declaration with no body.
public static native double sqrt(double a);
I double checked if StrictMath was an interface, which it was not, and that's when I noticed the native keyword.
Seems like methods declared native are not implemented in Java itself but can be in any natively available language
supported by the hardware the program is currently running on.
The JVM is free to either use a precompiled native library in any language (c, c++ mostly?) or to directly invoke platform
level assembly instructions.
For the brave, the square root function in C in Freely Distributable Library for Mathematical Functions(fdlibm) here /src/share/native/java/lang/fdlibm/src/e_sqrt.c
#include "fdlibm.h"
#ifdef __STDC__
static const double one = 1.0, tiny=1.0e-300;
#else
static double one = 1.0, tiny=1.0e-300;
#endif
#ifdef __STDC__
double __ieee754_sqrt(double x)
#else
double __ieee754_sqrt(x)
double x;
#endif
{
double z;
int sign = (int)0x80000000;
unsigned r,t1,s1,ix1,q1;
int ix0,s0,q,m,t,i;
ix0 = __HI(x); /* high word of x */
ix1 = __LO(x); /* low word of x */
/* take care of Inf and NaN */
if((ix0&0x7ff00000)==0x7ff00000) {
return x*x+x; /* sqrt(NaN)=NaN, sqrt(+inf)=+inf
sqrt(-inf)=sNaN */
}
/* take care of zero */
if(ix0<=0) {
if(((ix0&(~sign))|ix1)==0) return x;/* sqrt(+-0) = +-0 */
else if(ix0<0)
return (x-x)/(x-x); /* sqrt(-ve) = sNaN */
}
/* normalize x */
m = (ix0>>20);
if(m==0) { /* subnormal x */
while(ix0==0) {
m -= 21;
ix0 |= (ix1>>11); ix1 <<= 21;
}
for(i=0;(ix0&0x00100000)==0;i++) ix0<<=1;
m -= i-1;
ix0 |= (ix1>>(32-i));
ix1 <<= i;
}
m -= 1023; /* unbias exponent */
ix0 = (ix0&0x000fffff)|0x00100000;
if(m&1){ /* odd m, double x to make it even */
ix0 += ix0 + ((ix1&sign)>>31);
ix1 += ix1;
}
m >>= 1; /* m = [m/2] */
/* generate sqrt(x) bit by bit */
ix0 += ix0 + ((ix1&sign)>>31);
ix1 += ix1;
q = q1 = s0 = s1 = 0; /* [q,q1] = sqrt(x) */
r = 0x00200000; /* r = moving bit from right to left */
while(r!=0) {
t = s0+r;
if(t<=ix0) {
s0 = t+r;
ix0 -= t;
q += r;
}
ix0 += ix0 + ((ix1&sign)>>31);
ix1 += ix1;
r>>=1;
}
r = sign;
while(r!=0) {
t1 = s1+r;
t = s0;
if((t<ix0)||((t==ix0)&&(t1<=ix1))) {
s1 = t1+r;
if(((t1&sign)==sign)&&(s1&sign)==0) s0 += 1;
ix0 -= t;
if (ix1 < t1) ix0 -= 1;
ix1 -= t1;
q1 += r;
}
ix0 += ix0 + ((ix1&sign)>>31);
ix1 += ix1;
r>>=1;
}
/* use floating add to find out rounding direction */
if((ix0|ix1)!=0) {
z = one-tiny; /* trigger inexact flag */
if (z>=one) {
z = one+tiny;
if (q1==(unsigned)0xffffffff) { q1=0; q += 1;}
else if (z>one) {
if (q1==(unsigned)0xfffffffe) q+=1;
q1+=2;
} else
q1 += (q1&1);
}
}
ix0 = (q>>1)+0x3fe00000;
ix1 = q1>>1;
if ((q&1)==1) ix1 |= sign;
ix0 += (m <<20);
__HI(z) = ix0;
__LO(z) = ix1;
return z;
}
Good luck understanding that!
There are roughly around 300 odd native methods in the base package of JDK 8.
Things changed slowly from JDK 9.
The number of native methods slightly reduced, could be because of them getting replaced with Java only implementations.
The Math class implementations of pow, hypot, cbrt which earlier dependent on native implementation are now defined in FdLibm.java.
This porting of methods from fdlibm to Java seems to have began late 2015 thru 2016. Some of the methods made it to the JDK 9 release, while others (including the square root function) to JDK 21 6 years later.
JDK 9 also introduced the @HotSpotIntrinsicCandidate
annotation;
Indicates that an annotated method may be (but is not guaranteed to be) intrinsified by the HotSpot VM. A method is intrinsified if the HotSpot VM replaces the annotated method with hand-written assembly and/or hand-written compiler IR -- a compiler intrinsic -- to improve performance
From JDK 16, this is now just @IntrinsicCandidate.
Fast forward in 2025, with JDK 25, there are only about 220 native methods in the base package.