Sayan Sayan - 13 days ago 6
Java Question

Efficient 10 power x algorithm

Can anyone help me with finding an efficient code to find 10 power x?

private int power(int base, int exp)
{
int result = 1;
while (exp != 0)
{
if ((exp & 1) == 1)
result *= base;
exp >>= 1;
base *= base;
}

return result;
}


Source of code from here, but I am looking for a way where the input could be 3.14 (double). I also cannot use any library functions. The power can be a real number. So it is not just a simple integer algorithm where we can find by Exponentiation by Squaring.

Answer

Instead of calculating 10^x you can calculate e^(x*ln(10)). So your question boil down to this one. I can offer a simple implementation by calculating the Taylor series:

double tenPow(double x) {
    // ln(10)
    double logTen = 2.3025850929940456840179914546843642076011014886287729;
    double sum = 0.;
    x *= logTen; // x * ln(10)
    double tmp = 1.;
    for (double i = 1.; tmp > 0.; i += 1.) {
        sum += tmp;
        tmp *= x;
        tmp /= i;
    }
    return sum;
}

EDIT1 As noted in the comment this method is not effective for large x. But we can break x into its integer and fractional parts, so x = xi + xf. e^(xi + xf) = e^xf * e^xi. e^xi can be effectively calculated using recursive exponentiation. And e^xf can be calculated using the Taylor series.

EDIT2 Here is my implementation of this algorithm:

public static double fastTenPow(double x) {
    if (x < 0.) {
        return 1. / fastTenPow(-x);
    }
    int intPart = (int) x;
    double fractPart = x - intPart;
    return fractTenPow(fractPart) * intTenPow(intPart);
}

private static double intTenPow(int x) { // copied it
    double res = 1.;
    double base = 10.;
    while (x != 0) {
        if ((x & 1) == 1) {
            res *= base;
        }
        x >>= 1;
        base *= base;
    }
    return res;
}

private static final double LOG_TEN = 2.3025850929940456840179914546843642076011014886287729;
private static final double EPS = 0.00000000000000001;

private static double fractTenPow(double x) {
    double sum = 0.;
    x *= LOG_TEN;
    double tmp = 1.;
    for (double i = 1.; tmp > EPS; i += 1.) {
        sum += tmp;
        tmp *= x;
        tmp /= i;
    }
    return sum;
}
Comments