Sayan - 1 year ago 103
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.

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;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download