Fixing the performance time of algorithm

The following program is created to to calculate the perfect power of numbers

The end result is to have the Perfect Power complete all test cases in under .01s of elapsed execution time.

Currently the program end result time performance is at about 2+secs for 10,000 and the one for 1073741824 takes much much longer. Need assistance to help lower the time for all perfect-powers to be .01 seconds and less.

Below is the program code:

    /**
*
* A utlity class to calculate the perfect power of an integer
*/
public class PerfectPower {
public static void main(String[] args) {
new TimeExec(new Runnable() {
public void run() {
System.out.println("Perfect Power of 17 is " + getPerfectPower(17));
}
}, "Get Perfect Power of 17", System.out).start();
new TimeExec(new Runnable() {
public void run() {
System.out.println("Perfect Power of 625 is " + getPerfectPower(625));
}
}, "Get Perfect Power of 625", System.out).start();
new TimeExec(new Runnable() {
public void run() {
System.out.println("Perfect Power of 1024 is " + getPerfectPower(1024));
}
}, "Get Perfect Power of 1024", System.out).start();
new TimeExec(new Runnable() {
public void run() {
System.out.println("Perfect Power of 10000 is " + getPerfectPower(10000));
}
}, "Get Perfect Power of 10000", System.out).start();
new TimeExec(new Runnable() {
public void run() {
System.out.println("Perfect Power of 1073741824 is " + getPerfectPower(1073741824));
}
}, "Get Perfect Power of 1073741824", System.out).start();	
}
/**
* Get the perfect power for a number.
* @param x number for which to calculate the perfect power.
*/
public static int getPerfectPower(int x) {
int largestP = 1;
for (int b = 1; b < x; b++) {
for (int p = 1; p < x; p++) {
if (Math.pow(b,p) == x) {
largestP = p;
}
}           
}
return largestP;
}
}

end code:

Perfect Power of 17 is 1
TimeExec: Get Perfect Power of 17: 0.001s

Perfect Power of 625 is 2
TimeExec: Get Perfect Power of 625: 0.026s

Perfect Power of 1024 is 2
TimeExec: Get Perfect Power of 1024: 0.052s

Perfect Power of 10000 is 2
TimeExec: Get Perfect Power of 10000: 1.9s

need this code here to print under .01s
Perfect Power of 1073741824 is X
TimeExec: Get Perfect Power of : XX.XXXs

First, we're looking for the maximum exponent for the perfect power number given in the parameter. The best candidate for the maximum exponent is a base of 2, so we'll start the loop at 2, not 1.

Second, the smallest exponent is 2 (other than the fallback 1), so the maximum base where base² = x, is maxBase = sqrt(x), so we'll end the loop at that base value.

We're targeting the formula b^p = x, and we have x from parameter and b from the loop, so we can calculate p using p = log(x) / log(b), then check if that's an integer.

Best way to do that, avoiding rounding errors, is to round to nearest integer, then checking if b^p == x.

The code for that is:

public static int getPerfectPower(int x) {
double maxBase = Math.sqrt(x);
for (int b = 2; b <= maxBase; b++) {
long p = Math.round(Math.log(x) / Math.log(b));
if (Math.pow(b, p) == x)
return (int) p;
}
return 1;
}

Tests

public static void main(String[] args) {
test(17);
test(625);
test(1024);
test(10000);
test(1073741824);
}
static void test(int x) {
long start = System.nanoTime();
int exponent = getPerfectPower(x);
long end = System.nanoTime();
System.out.printf("Perfect Power of %d is %d (%.9fs)%n",
x, exponent, (end - start) / 1e9);
}

Output

Perfect Power of 17 is 1 (0.000022500s)
Perfect Power of 625 is 4 (0.000003700s)
Perfect Power of 1024 is 10 (0.000003700s)
Perfect Power of 10000 is 4 (0.000003500s)
Perfect Power of 1073741824 is 30 (0.000001700s)

Alternatively, we can loop the exponent instead of the base, changing time complexity from O(sqrt(x)) to O(log(x)), which is technically faster, but the values here are too small to notice any performance difference.

Without further explanation, here's the code:

public static int getPerfectPower(int x) {
// x = b ^ p   <==>   p = log(x) / log(b)   <==>   b = exp(log(x) / p)
double logX = Math.log(x);
int maxExp = (int) Math.round(logX / Math.log(2));
for (int p = maxExp; p > 1; p--) {
long b = Math.round(Math.exp(logX / p));
if (Math.pow(b, p) == x)
return p;
}
return 1;
}

You are testing too many cases with the nested two loops from 1 to x.

For an exponent p you can compute the most likely base as b0=floor(pow(x,1.0/p)). If you want to be cautious then test the powers of b=b0-1, b0, b0+1 for being equal to x, but the case b=b0-1 should never be valid.

You can then stop increasing the exponents when b0=1 has been reached.