Need help in translating code from C to Java.

Question

From this article. Here's the code:

float InvSqrt(float x){ // line 0
   float xhalf = 0.5f * x;
   int i = *(int*)&x; // store floating-point bits in integer
   i = 0x5f3759d5 - (i >> 1); // initial guess for Newton's method
   x = *(float*)&i; // convert new bits into float
   x = x*(1.5f - xhalf*x*x); // One round of Newton's method
   return x;
}

...I can't even tell if that's C or C++. [okay apparently it's C, thanks] Could someone translate it to Java for me, please? It's (only, I hope) lines 2 and 4 that are confusing me.

Answer 1

The code you quote is C, although the comments are C++-style.

What the code is doing involves knowledge of the way floating-point values are stored, at the bit level. The "magic number" 0x5f3759d5 has something do with a particular value.

The floating point x value's bits are accessed when i is initialized, because the address of x is dereferenced. So, i is loaded with the first 32 bits of the floating point value. On the next line, x is written with the contents of i, updating the working approximation value.

I have read that this code became popular when John Carmack released it with Id's open source Quake engine. The purpose of the code is to quickly calculate 1/Sqrt(x), which is used in lighting calculations of graphic engines.

I would not have been able to translate this code directly to Java because it uses "type punning" as described above -- when it accesses the float in memory as if it were an int. Java prevents that sort of activity, but as others have pointed out, the Float object provides methods around it.

The purpose of using this strange implementation in C was for it to be very fast. At the time it was written, I imagine a large improvement came from this method. I wonder if the difference is worth it today, when floating point operations have gotten faster.

Using the Java methods to convert float to integer bits and back may be slower than simply calculating the inverse square root directly using Java math function for square root.

Answer 2

You want to use these methods:

• Float.floatToIntBits
• Float.intBitsToFloat

And there may be issues with strictfp, etc.

It's roughly something like this: (CAUTION: this is untested!)

float InvSqrt(float x){ // line 0
   float xhalf = 0.5f * x;
   int i = Float.floatToIntBits(x); // store floating-point bits in integer
   i = 0x5f3759d5 - (i >> 1); // initial guess for Newton's method
   x = Float.intBitsToFloat(i); // convert new bits into float
   x = x*(1.5f - xhalf*x*x); // One round of Newton's method
   return x;
}

Answer 3

Those lines are used to convert between float and int as bit patterns. Java has static methods in java.lang.Float for that - everything else is identical.

static float InvSqrt(float x) { // line 0
    float xhalf = 0.5f * x;
    int i = Float.floatToIntBits(x); // store floating-point bits in integer
    i = 0x5f3759d5 - (i >> 1); // initial guess for Newton's method
    x = Float.intBitsToFloat(i); // convert new bits into float
    x = x * (1.5f - xhalf * x * x); // One round of Newton's method
    return x;
}

Answer 4

The lines you care about are pretty simple. Line 2 takes the bytes in float x, which are in some floating-point representation like IEEE754, and stores them in an integer, exactly the way they are. This will result in a totally different number, since integers and floats are represented differently in byte form. Line 4 does the opposite, and transfers the bytes in that int to the float again

Answer 5

Ok I'm going out on a limb here, because I know C but I don't know Java.

Literally rewriting this C code in Java is begging for trouble. Even in C, the code is unportable. Among other things it relies on: The size of floating point numbers. The size of integers. The internal representation of floating point numbers. The byte alignment of both floating point numbers and integers. Right shift ( i.e. i>>1) being implemented using logical right shift as opposed to arithmetic right shift (which would shift in a 1 on integers with a high order 1 bit and thus no longer equate to divide by 2).

I understand Java compiles to a bytecode rather than directly to machine code. Implementers of byte code interpreters tune using assumptions based on the spec for the byte code and an understanding of what is output by the compiler from sensible input source code.

Hacks like this don't fall under the umbrella "sensible input source".

There is no reason to expect the interpreter will perform faster with your C hack, in fact there is a good chance it will be slower.

My advice is: IGNORE The C code.

Look for a gain in efficiency that is Java centric.

The concept of the C hack is:

Approximate 1/square(x) by leveraging knowledge that the internal representation of floating point numbers already has the exponent broken out of the number, exponent(x)/2 is faster to compute than root(x) if you already have exponent(x).

The hack then performs one iteration of newton's method to reduce the error in the approximation. I Presume one iteration reduced the error to something tolerable.

Perhaps the concept warrants investigation in Java, but the details will depend on intimate knowledge of how JAVA is implemented, not how C is implemented.