Fast Function resembling a^b

Question

This is kind of obscure, but I need a function that can be computed very quickly and resembles a^b where a is between 0 and 1 and b is very large. It will be calculated for one a at a time for many b's. Ideally, the result would be within 0.4%. Thanks in advance.

Answer 1

Pulling my comments into an answer:

Since you mention that b is large enough to be rounded to an integer, then one approach is to use the Binary Exponentiation algorithm by squaring.

Math.pow() is slow because it needs to handle non-integral powers. So might be possible to do better in your case because you can utilize the integer powering algorithms.

---

As always, benchmark your implementation to see if it actually is faster than Math.pow().

---

Here's an implementation that the OP found:

public static double pow(double a, int b) {
    double result = 1;
    while(b > 0) {
        if (b % 2 != 0) {
            result *= a;
            b--;
        } 
        a *= a;
        b /= 2;
    }

    return result;

}

---

Here's my quick-and-dirty (unoptimized) implementation:

public static double intPow(double base,int pow){
    int c = Integer.numberOfLeadingZeros(pow);

    pow <<= c;

    double value = 1;
    for (; c < 32; c++){
        value *= value;
        if (pow < 0)
            value *= base;
        pow <<= 1;
    }

    return value;
}

This should work on all positive pow. But I haven't benchmarked it against Math.pow().

Answer 2

For your specific case ("calculated for one a at a time for many b's") I would suggest following approach:

Prepare table data to be used later in particular calculations:

• determine N such that 2^N is less than b for each possible b.

• calculate table t: t[n]=a^(2^n) for each n which is less than N. This is effectively done as t[k+1]=t[k]*t[k].

Calculate a^b:

• using binary representation of b, compute a^b as t[i1]t[i2]...*t[ik] where i1..ik are positions of non-zero bits in binary representation of b.

The idea is to reuse values of a^(2^n) for different b's.

Answer 3

Apache FastMath offers double pow(double d, int e) function for case when the exponent is an integer.

The implementation is based on Veltkamp's TwoProduct algorithm. The usage is similar to standard Math.pow function:

import org.apache.commons.math3.util.FastMath;
// ...
FastMath.pow(3.1417, 2);