Finding b and e such that b to the power of e is closest to a given number

The question is to find a number with absolute minimum difference from a number of the form be. I came up with the below code which takes 4 seconds to solve each test case on an average however it has to be solved within 2 seconds.

Sample Input:


11

25

Sample Output:


2
0

Explanation:

11 is the nearest to 32. Thus 11 - 9 = 2

25 is 52 thus there is no difference.

My code:

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int T = in.nextInt();    //Number of testcases

    for(int i = 0; i < T; i++){

            int number = in.nextInt();

            int sqrtNumber = (int)Math.sqrt(number);                
            int powerNumber; 

            int minDiff = Integer.MAX_VALUE;
            for (int b = 2; b <= sqrtNumber; b++) {
                for (int e = 1; (powerNumber = (int) Math.pow(b, e)) <= number; e++) {
                    if (number - powerNumber < minDiff)
                        minDiff = number - powerNumber;
                }
            }
            System.out.println(minDiff);

    }
}

A big performance improvement can be made when you realize you don't need to loop over all the possible exponent e. The code calculates, for each possible e, the value of be, and calculating that power takes time.

The goal here is to find b and e such that be is the closest to an integer n. If we rewrite this, it also means finding b and e where \$e\log{b}\$ is closest to \$\log{n}\$. So for a given input number n, and a given base b, we know that the closest value we're looking for will have an exponent of \$e = \left\lfloor\frac{\log{n}}{\log{b}}\right\rfloor\$.

JS1 rightfully pointed out that calculating this formula can lead to rounding errors. Since we're dealing with whole numbers, we can add 0.5 before calculating the logarithm to account for that (I tested this for all numbers from 5 to 1000000). As such, for the inner loop, you can just have:

int sqrtNumber = (int) Math.sqrt(number);
double logN = Math.log(number + 0.5); // to account for rounding issues

int minDiff = Integer.MAX_VALUE;
for (int b = 2; b <= sqrtNumber; b++) {
    int e = (int) (logN / Math.log(b));
    int powerNumber = (int) Math.pow(b, e);
    if (number - powerNumber < minDiff) {
        minDiff = number - powerNumber;
    }
}

This code only makes a single power calculation, in order to know the actual difference between the power and the target number.

Here's a result of a JMH benchmark, comparing the initial code in the question and this revised code. The input number tested is 15000, 150000 and 1500000. This is very far to take 4 seconds for each case, but the revised code is 5 times faster (Windows 10, JDK 1.8.0_102 64 bits, i5 CPU @ 2.90 GHz).

Benchmark           (number)  Mode  Cnt  Score    Error  Units
StreamTest.initial     15000  avgt   30  0,023 ±  0,001  ms/op
StreamTest.initial    150000  avgt   30  0,068 ±  0,002  ms/op
StreamTest.initial   1500000  avgt   30  0,202 ±  0,002  ms/op
StreamTest.revised     15000  avgt   30  0,005 ±  0,001  ms/op
StreamTest.revised    150000  avgt   30  0,014 ±  0,001  ms/op
StreamTest.revised   1500000  avgt   30  0,041 ±  0,001  ms/op

Code of benchmark for completeness:

@Warmup(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Fork(3)
public class StreamTest {

    @State(Scope.Benchmark)
    public static class NumberContainer {

        @Param({ "15000", "150000", "1500000" })
        private int number;

    }

    static int initialCode(int number) {
        int sqrtNumber = (int)Math.sqrt(number);                
        int powerNumber; 
        int minDiff = Integer.MAX_VALUE;
        for (int b = 2; b <= sqrtNumber; b++) {
            for (int e = 1; (powerNumber = (int) Math.pow(b, e)) <= number; e++) {
                if (number - powerNumber < minDiff)
                    minDiff = number - powerNumber;
            }
        }
        return minDiff;
    }

    static int revisedCode(int number) {
        int sqrtNumber = (int) Math.sqrt(number);
        double logN = Math.log(number + 0.5);
        int minDiff = Integer.MAX_VALUE;
        for (int b = 2; b <= sqrtNumber; b++) {
            int e = (int) (logN / Math.log(b));
            int powerNumber = (int) Math.pow(b, e);
            if (number - powerNumber < minDiff) {
                minDiff = number - powerNumber;
            }
        }
        return minDiff;
    }

    @Benchmark
    public int initial(NumberContainer c) {
        return initialCode(c.number);
    }

    @Benchmark
    public int revised(NumberContainer c) {
        return revisedCode(c.number);
    }

}

StackExchange Code Review Q#138629, answer score: 4