Here is an inheritence graph of some of the more important Java collection classes of Java 1.5. Instantiateable classes are blue and rectangular, abstract classes are just rectangular, and interfaces are elliptic. Click on the image for a printable size:

Java 1.5 Collections Hierarchy

As a sidenote, have written this post almost a year ago and just found it in my drafts. I have completely forgotten about it! So here it is anyways. And now I remember why I did not post it: becauseit contains only a minor subset of the collections! Thanks Artur Biesiadowski for reminding me about that…

Yesterday I have played a bit with reinventing a fast approximation for sqrt() in Java. This might be handy with J2ME. Wikipedia has a nice article about Approximations that depend on IEEE representation. My version works, and on my Intel Dual Core with an average error of 1.57%, maximum error 4.02% it is 3.5 times faster than the original sqrt. In addition, it is very simple to improve the precision to 0.000161% average error and 0.000775% maximum error which is then 1.56 times faster than Math.sqrt().

Sourcecode

I use floating point tricks based on my pow() approximation. Basically I just took the pow() formula and for a^b I substitued b with 0.5, then simplified this as much as possible. As it turns out the result is very simple and short. This initial approximation can be easily made more precise with Newton’s method:

    public static double sqrt(final double a) {
        final long x = Double.doubleToLongBits(a) >> 32;
        double y = Double.longBitsToDouble((x + 1072632448) << 31);

        // repeat the following line for more precision
        //y = (y + a / y) * 0.5;
        return y;
    }

Here is a comparison of the performance and accurancy versus the number of repetitions:

With 2 repetitions, the trouble is not worth the effort, as the approximation is already slower than the original Math.sqrt() which is more precise.

Use Case

Imagine you have some Java code that does lots and lots of computation. All the time intensive calculations is performed by the class SlowCalculator which implements the interface Calculator:

public static interface Calculator {
    public String calculate(int a, String b);
}

public static void main(String[] args) {
    Calculator c = new SlowCalculator();
    // call c.calculate() a lot of times here...
}

You notice that calculate() is often called with the same parameters which lead to the exact same result (SlowCalculator is stateless). This means it is possible to cache values so there’s no need to recompute. Using the generic CachingProxy™ described below, you can create a cached proxy for any class with just one single line of code:

// ...

public static void main(String[] args) {
    Calculator c = new SlowCalculator();
    c = CachedProxy.create(Calculator.class, c);
    // call c.calculate() a lot of times here...
}

That’s it, and the application is blazingly fast again.

UPDATE: Support for null values, transparently handles exceptions, better hash, nullpointer-bugfix.

UPDATE: Here is an article “Memoization in Java Using Dynamic Proxy Classes” that does (almost) exactly the same as this code.

Read more

I have already written about approximations of e^x, log(x) and pow(a, b) in my post Optimized Exponential Functions for Java. Now I have more In particular, the pow() function is now even faster, simpler, and more accurate. Without further ado, I proudly give you the brand new approximation:

Approximation of pow() in Java

public static double pow(final double a, final double b) {
    final int x = (int) (Double.doubleToLongBits(a) >> 32);
    final int y = (int) (b * (x - 1072632447) + 1072632447);
    return Double.longBitsToDouble(((long) y) << 32);
}

This is really very compact. The calculation only requires 2 shifts, 1 mul, 2 add, and 2 register operations. That’s it! In my tests it usually within an error margin of 5% to 12%, in extreme cases sometimes up to 25%. A careful analysis is left as an exercise for the reader. This is very usable for in e.g. metaheuristics or neural nets.

I use Linux, Java 1.6.0-b105 with the server VM, and execute the benchmark with this command:

sudo nice -n -20 java -cp . -server PowTest

The approximation is 27 times faster than Math.pow() on my Pentium-M. On a Pentium 4 it is 41 times faster. Unfortunately, microbenchmarks are difficult to do in Java, so your mileage may vary. You can download the benchmark PowTest.java and have a look, I have tried to prevent overoptimization while still having a low overhead.

Approximation of pow() in C and C++

double pow(double a, double b) {
    int tmp = (*(1 + (int *)&a));
    int tmp2 = (int)(b * (tmp - 1072632447) + 1072632447);
    double p = 0.0;
    *(1 + (int * )&p) = tmp2;
    return p;
}

Compiled on my Pentium-M with gcc 4.1.2:

gcc -O3 -march=pentium-m -fomit-frame-pointer -fno-strict-aliasing

This version is 7.8 times faster than pow() from the standard library.

WARNING! you HAVE to use the -fno-strict-aliasing option, or this does not work!

Approximation of pow() in C#

Jason Jung has posted a port of the this code to C#:

public static double PowerA(double a, double b) {
  int tmp = (int)(BitConverter.DoubleToInt64Bits(a) >> 32);
  int tmp2 = (int)(b * (tmp - 1072632447) + 1072632447);
  return BitConverter.Int64BitsToDouble(((long)tmp2) << 32);
}

How the Approximation was Developed

It is quite impossible to understand what is going on in this function, it just magically works. To shine a bit more light on it, here is a detailed description how I have developed this.

Approximation of e^x

As described here, the paper “A Fast, Compact Approximation of the Exponential Function” develops a C macro that does a good job at exploiting the IEEE 754 floating-point representation to calculate e^x. This macro can be transformed into Java code straightforward, which looks like this:

public static double exp(double val) {
    final long tmp = (long) (1512775 * val + (1072693248 - 60801));
    return Double.longBitsToDouble(tmp << 32);
}

Use Exponential Functions for a^b

Thanks to the power of math, we know that a^b can be transformed like this:

1. Take exponential

   a^b = e^(ln(a^b))

2. Extract b

   a^b = e^(ln(a)*b)

Now we have expressed the pow calculation with e^x and ln(x). We already have the e^x approximation, but no good ln(x). The old approximation is very bad, so we need a better one. So what now?

Approximation of ln(x)

Here comes the big trick: Rember that we have the nice e^x approximation? Well, ln(x) is exactly the inverse function! That means we just need to transform the above approximation so that the output of e^x is transformed back into the original input.

That’s not too difficult. Have a look at the above code, we now take the output and move backwards to undo the calculation. First reverse the shift:

final double tmp = (Double.doubleToLongBits(val) >> 32);

Now solve the equation

tmp = (1512775 * val + (1072693248 - 60801))

for val:

1. The original formula

   tmp = (1512775 * val + (1072693248 - 60801))

2. Perform subtraction

   tmp = 1512775 * val + 1072632447

3. Bring value to other side

   tmp - 1072632447 = 1512775 * val

4. Divide by factor

   (tmp - 1072632447) / 1512775 = val

5. Finally, val on the left side

   val = (tmp - 1072632447) / 1512775

Voíla, now we have a nice approximation of ln(x):

public double ln(double val) {
    final double x = (Double.doubleToLongBits(val) >> 32);
    return (x - 1072632447) / 1512775;
}

Combine Both Approximations

Finally we can combine the two approximations into e^(ln(a) * b):

public static double pow1(final double a, final double b) {
    // calculate ln(a)
    final double x = (Double.doubleToLongBits(a) >> 32);
    final double ln_a = (x - 1072632447) / 1512775;

    // ln(a) * b
    final double tmp1 = ln_a * b;

    // e^(ln(a) * b)
    final long tmp2 = (long) (1512775 * tmp1 + (1072693248 - 60801));
    return Double.longBitsToDouble(tmp2 << 32);
}

Between the two shifts, we can simply insert the tmp1 calculation into the tmp2 calculation to get

public static double pow2(final double a, final double b) {
    final double x = (Double.doubleToLongBits(a) >> 32);
    final long tmp2 = (long) (1512775 * (x - 1072632447) / 1512775 * b + (1072693248 - 60801));
    return Double.longBitsToDouble(tmp2 << 32);
}

Now simplify tmp2 calculation:

1. The original formula

   tmp2 = (1512775 * (x - 1072632447) / 1512775 * b + (1072693248 - 60801))

2. We can drop the factor 1512775

   tmp2 = (x - 1072632447) * b + (1072693248 - 60801)

3. And finally, calculate the substraction

   tmp2 = b * (x - 1072632447) + 1072632447

The Result

That’s it! Add some casts, and the complete function is the same as above.

public static double pow(final double a, final double b) {
    final int tmp = (int) (Double.doubleToLongBits(a) >> 32);
    final int tmp2 = (int) (b * (tmp - 1072632447) + 1072632447);
    return Double.longBitsToDouble(((long) tmp2) << 32);
}

This concludes my little tutorial on microoptimization of the pow() function. If you have come this far, I congratulate your presistence

UPDATE Recently there several other approximative pow calculation methods have been developed, here are some others that I have found through reddit:

• Fast pow() With Adjustable Accuracy — This looks quite a bit more sophisticated and precise than my approximation. Written in C and for float values. A Java port should not be too difficult.
• Fast SSE2 pow: tables or polynomials? — Uses SSE operation and seems to be a bit faster than the table approach from the link above with the potential to scale better when due to less cache usage.

Please post what you think about this!

The Javadoc Search Engine now searches JDK 7 too:

• Go here: javadoc.ankerl.com

It’s still a draft, so the documentation is surely subject to change. You can also use the search directly from here:

happy hacking!