FastInverseSquareRootTest

FastInverseSquareRootTest.java

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();
    }
}

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()