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.