math_utils
Class MathUtils

java.lang.Object
  math_utils.MathUtils

public class MathUtils
extends java.lang.Object

Misc mathematical functions.

Author:

chaiml

Field Summary

static int	EXPAPPROX_PRECISION_BITS Number of bits to use in each mantissa block for the approximation in expApprox().
static double	LN2
static int	LOG2APPROX_PRECISION_BITS Number of most significant bits to use from the mantissa for the approximation in log2approx().

Constructor Summary

MathUtils()

Method Summary

static double	expApprox(double x) An efficient version of the exponential function, approximates the value of exp(x).
static double	log2approx(double x) An efficient version of the logarithm function, approximates the value of log_2(x).
static double	powApprox(double loga, double b) An efficient version of the power function, approximates the value of pow(a,b).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

LOG2APPROX_PRECISION_BITS

public static final int LOG2APPROX_PRECISION_BITS

Number of most significant bits to use from the mantissa for the approximation in log2approx().

See Also:

Constant Field Values

EXPAPPROX_PRECISION_BITS

public static final int EXPAPPROX_PRECISION_BITS

Number of bits to use in each mantissa block for the approximation in expApprox().

See Also:

Constant Field Values

LN2

public static final double LN2

Constructor Detail

MathUtils

public MathUtils()

Method Detail

log2approx

public static double log2approx(double x)

An efficient version of the logarithm function, approximates the value of log_2(x). This function is about 8-10 times faster than Math.log(). The returned value approximates the real value within +-0.0001: | Math.log(x)/Math.log(2.0) - MathUtils.log2approx(x) | < 0.0001 (actually, the difference is bounded by log2(1+1/(1.5*2^LOG2APPROX_PRECISION_BITS)). Method: A (positive) double is represented as 1.M*2^E, where M is the mantissa and E is the exponent. Thus, log2(1.M*2^E) = log2(1.M) + E So, by looking at the binary representation of the double, we can easily extract E; and, using a pre-computed cache, we get log2(1.M'), where M' is the most significant bits of M.

Parameters:

x -

Returns:

an approximation of log_2(x); if x is non-positive or Nan, an arbitrary value is returned.

expApprox

public static double expApprox(double x)

An efficient version of the exponential function, approximates the value of exp(x). This function is about 3-4 times faster than Math.exp(). The returned value approximates the real value with ratio 1.001: 1/1.001 < Math.exp(x) / MathUtils.expApprox(x) < 1.001 For values of x that aren't too large or too small, the approximation is better, e.g., if x is between -10 and 10, the ratio is 1.00001. Method: A double x is represented as S*1.M*2^E, where S is the sign bit, M is the mantissa and E is the exponent. We break the mantissa into several blocks: M1 contains the 5 most significant bits of M, M2 contains the next 5 significant bits, and so on. Thus: x=S*(1+M1+M2+...)*2^E. So: exp(x) = exp(S*(1+M1)*2^E) * exp(S*M2*2^E) * ... Each of the exp()'s in the above product is pre-computed and saved in an array of size 2^L, where L=1+11+5 (1 for the sign bit, 11 for the exponent, and 5 bits for the mantissa block); Using four blocks from the mantissa, i.e., a total of 20 bits from the mantissa, the maximum ratio between the correct exp(x) and the approximated result we get is (for positive numbers): exp(2^-20 * 2^E) = exp(2^E-20) ; now, the largest number a double can hold is ~2^1024=~e^709, so we can assume that x < 709, which means that E < 10. Therefore, the approximation ratio is at most exp(2^-10)=~1.001. For small x, the ratio is better.

Parameters:

x -

Returns:

an approximation of exp(x)

powApprox

public static double powApprox(double loga,
                               double b)

An efficient version of the power function, approximates the value of pow(a,b). This function receives the paramters log(a),b and approximates a^b. It uses the expApprox() method, so the approximation ratio is the same as there. There are 3 ways to use this function: (1) If a is fixed, then you could pre-compute loga=Math.log(a), and call powApprox(loga,b) (2) If a is variable, and you'd like a good approximation, then use: powApprox(Math.log(a),b) (3) If a is variable, and you don't require a good approximation, then use: powApprox(MathUtils.log2approx(a)*MathUtils.LN2,b) Method (1) is ~10 times faster than Math.pow(); (2) is ~2.5 times faster; (3) is ~5 times faster. Note that in method (3) the approximation ratio is e1*exp(+/-b*LN2*e2), where e1 and e2 are the approximations guaranteed by expApprox() and log2approx(), respectively.