Usually microoptimization is only done in C or C++, but it works quite well in Java too. For a project I needed very fast log() and exp() calculations, and Java’s Math.log() and Math.exp() just doesn’t cut it. After a bit of research I have found the following approximations that are good enough for me:
UPDATE This pow() approximation is obsolete. I have a much faster and more accurate approximation version here.
Fast Exponential Function in Java
The paper “A Fast, Compact Approximation of the Exponential Function” describes a C macro that does a good job at exploiting the IEEE 754 floating-point representation to calculate e^x. I have transformed the macro into Java code:
public static double exp(double val) {
final long tmp = (long) (1512775 * val + 1072632447);
return Double.longBitsToDouble(tmp << 32);
}This code is 5.3 times faster than Math.exp() on my computer. Beware that it is only an approximation, for a detailed analysis read the paper.
Fast Natural Logarithm in Java
I have found the following approximation here, and there is not much information about it except that it is called “Borchardt’s Algorithm” and it is from the book “Dead Reconing: Calculating without instruments”. The approximation is not very good (some might say very bad…), it gets worse the larger the values are. But the approximation is also a monotonic, slowly increasing function, which is good enough for my use case.
public static double log(double x) {
return 6 * (x - 1) / (x + 1 + 4 * (Math.sqrt(x)));
}This approximation is 11.7 times faster than Math.log().
Fast Power Calculation
Equiped with these optimized functions, it is possible to do several other optimizations. For example you can replace
Math.pow(a, b)
with
Math.exp(b * Math.log(a))
And then use the approximation functions for a highly optimized pow calculation. You can even combine the calculations and simplify it into this:
public static double pow(double a, double b) {
final long tmp = (long) (9076650 * (a - 1) / (a + 1 + 4 * (Math.sqrt(a))) * b + 1072632447);
return Double.longBitsToDouble(tmp << 32);
}This is 8.7 times faster than the Math.pow(a, b).
Accuracy
The above functions are very inaccurate, especially the log calculation. So before you use this code you have to test it if the approximation is good enough for you!
Have fun
Here are some benchmarks from a Pentium IV, doing 20 million calculations. On this machine I get an even better performance than stated above. I use Sun’s JRE 1.5.0_08.
6.233 sec, Math.log(val)
0.531 sec, 6*(x-1)/ (x + 1 + 4*(Math.sqrt(x)))
5.920 sec, Math.exp()
1.108 sec, exp optimized with IEEE 754 trick
15.967 sec, Math.pow(a, b)
11.014 sec, e^(b * log(a))
7.607 sec, e^(b * log(a)) + IEEE 754 trick
2.109 sec, e^(b * log(a)) + IEEE 754 trick + LOG approximation
1.827 sec, simplified everything
Pingback: Exponential Functions: Benchmarks, 11 Times Faster Math.pow() — Martin Ankerl
Thanks for this. Always good to get more performance tweaking out of Java. I use Processing for game dev in Java, and even with it’s use of Jikes, it could still use a boost.
Dr.E
http://www.turingshop.com/reports/01Java/
Pingback: Optimized pow() approximation for Java and C / C++ by Martin Ankerl
I have used the same trick for float, not double, with some slight modification to the constants to suite IEEE754 float format. The first constant for float is 1<<23/log(2) and the second is 127<<23 (for double they are 1<<20/log(2) and 1023<<20).
You don’t need to do the addition as floating point, I have move the braces around…
public static double exp(double val) { final long tmp = (long) (1512775 * val) + (1072693248 - 60801); return Double.longBitsToDouble(tmp << 32); }Additionally if you analyse the error there is a correlation to the mantissa of the result, which you can then correct for. The error is approximately (mantissa – mantissa^2)/2.9. Doing this all as integer math in fixed point format you get.
public static double exp(double val) { final long tmp = (long) (1512775 * val) + 1072693248; final long mantissa = tmp & 0x000FFFFF; int error = mantissa >> 7; // remove chance of overflow error = (error - a * a) / 186; // subtract mantissa^2 * 64 // 64 / 186 = 1/2.90625 return Double.longBitsToDouble((tmp - error) << 32); }PS hope this is valid Java, I converted from C.
The explain the shifting. The mantissa has 20 bits to the right of the decimal place. a is formed by shift right 7, leaving 13 bits to the right. When a is squared you double the number of decimal bits arriving at 26. Which is 20 bits times the scaling factor or 64 (6 bits). Now a squared matches error so the subtraction is valid.
@John
Hello,
i’m very interested by the accuracy optimization you suggested but i don’t undertand what is variable “a” in the expression :
error = (error – a * a) / 186;
Could you explain it please
Thanks
Michel Hummel
I think a is just mantissa. I’m guessing John started changing the variable name and forgot what he was doing.
The exp functions also seems to be working quite for J2ME which is lacking J2ME.
So if you’re writing say a game with projectiles traveling a certain trajectory it’s good enough
I confirm that those work with J2ME. Thanks to your math approximations I’ve been able to run Speex voice decoding on a mobile with a decent performance
glad that it’s working
I have inherited some code from a former employee. He has some code he calls
double powa(double x, double a)
which he says compute x^a for a close to 1.0.
The code is
double powa(double x, double a)
{
double lnx = log(x);
double am1 = a – 1;
double product = lnx * am1;
return (product + x * product^2 + x);
}
I at first thought he was using three terms of a Talor series about 1.0. However, it doesn’t seem to be that.
Where did this come from. BTW, I tested it and it does work, i.e. gives the same result as pow(x,a).