Math optimization (?)
Here is the method I would like to optimize. I am wondering if there is also a way to do this with bit shifting operators or the like?
publicstaticfinalint getMagnitude(double value){
return (int) (Math.ceil(Math.log10(value)));
}
// this version runs a bit faster since there is no division. but it is ugly
publicstaticfinalint getMagnitude(double value){
if (i < 0.000000001)
return -9;
elseif (i < 0.00000001)
return -8;
elseif (i < 0.0000001)
return -7;
elseif (i < 0.000001)
return -6;
elseif (i < 0.00001)
return -5;
elseif (i < 0.0001)
return -4;
elseif (i < 0.001)
return -3;
elseif (i < 0.01)
return -2;
elseif (i < 0.1)
return -1;
elseif (i < 0)
return 0;
elseif (i < 10)
return 1;
elseif (i < 100)
return 2;
elseif (i < 1000)
return 3;
elseif (i < 10000)
return 4;
elseif (i < 100000)
return 5;
elseif (i < 1000000)
return 6;
elseif (i < 10000000)
return 7;
elseif (i < 100000000)
return 8;
elseif (i < 1000000000)
return 9;
throw RuntimeException("unexpected value");
}
[3779 byte] By [
jvaudrya] at [2007-11-26 22:59:11]
# 1
The second method will not compile and both methods will not produce the same return values. Also, try providing 0 as a parameter to the first method.
You could put all those double values from the 2nd method in an array, and loop through the array. That way you don't need so many if/else-if statements.
Also, a (mathematical) magnitude cannot be negative.
Good luck.
Message was edited by:
prometheuzz
Never mind, I just tested it and the lookup-array is not faster.
# 3
> ...
> so absolute math percision is not necessary.
I mean there are different answers. Example: if the input is 100.0, the first method will return 2, the second method will return 3.
> I suppose an easier question would be: is there an
> way to find a magnitude without using log() functions?
There are numerous algorithms that'll find the log of a given value, but I doubt it will be faster than java.lang.Math's log10(...) method. Note that Java calls a native written method in java.lang.StrictMath in order to calculate it.
# 4
Faster is usually uglier in languages without macro systems. Call your function 'getOrderOfMagnitude' as magnitude x = Math.abs(x).
You could turn the if/else into a flatter binary tree (there's also if (i < 0) where if (i < 1.0)).
You may get an improvement taking the bits of the exponent of the double value and scaling them by ln(10)/ln(2) , which you can pre-calculate. But you may also need to inspect the mantissa, as the values of [0.5,1)*2^P may have different values of Q in [1,10)x10^Q for the same P.
There is also the possibility of using a short Taylor series for log10(x), taking only enough terms to get an error < 0.5. But I'd expect that to cost more than the decision trees.
A simple benchmark gives:
Total log10: 14201ms
Total skew tree:3136ms
Total balanced tree: 3264ms
Total bit pattern:2783ms
Total binary search on array:5654ms
Total linear search on array:4368ms
where the bal tree is a more balanced version of your if/else skew tree above, and the bit pattern version is: static final double LOG10_2 = Math.log(2) / Math.log(10);
public static final int getOrderOfMagnitude4 (double value) {
long bitpattern = Double.doubleToLongBits(value);
int exponent = (int) (bitpattern >> 52) & 0x7ff;
return (int)(exponent * LOG10_2) - 307;
}
which lacks the test on the mantissa, so sometimes gives the wrong answer, eg: 1.4867674791752066E-6 => -6 where your code gives -5. Adding that test would probably make it as slow as the others.
The array versions are slower than their equivalent unrolled decision trees. I suspect that the balanced tree/binary search are slower because it's harder to do branch prediction, and binary search requires more ops per loop, even though they are doing fewer double comparisons. (in the olden days double ops were much more expensive than integer ones, so it would be different).
So it seems the fastest version tested is your skew tree/unrolled linear loop/long list of if/else statements, unless you only want an approximation to the order of magnitude, in which case the bit-pattern approach wins.
Pete
# 5
Impressive work kirkham.
Another idea was to convert the double value to a long value since the values you are interested in are small.
long val2 = (long) value
boolean negate = false
if (value < 1) {
val2 = (long) (1.0 / value)
negate = true;
}
// now take the log of the long val2
// (not sure what the most efficient way to do that is
int log = // ...
if (negate) log = -log
return log;
