Effectively find smallest powers of given number

Question

Given number X, find numbers A and B such that X = A^B and A is the smallest possible number. B is less than 301.

String[] power2(String X) {
    double n = Double.parseDouble(X);
    double i = 1;
    double j = 1;
    String[] result = {"1", "1"};
    boolean flag = false;
    if (n > 1) {
        for (i = 1; i < n; i++) {
            for (j = 1; j < 301; j++) {
                if (Math.pow(i, j) == n) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                break;
            }
        }
    }
    result[0] = i + "";
    result[1] = j + "";
    return result;
}

This works fine but its not efficient.I am looking for more faster algorithm.

Answer 1

A couple of things:

1. Your current solution does not work. You don't consider case when b = 1, e.g. 100003 = 100003 ^ 1 but your function returns [100003.0, 301.0]. Due to loss of precision on doubles, your function will not return a valid result for 10000000000600000000009 = 100000000003 ^ 2. It will keep increasing base for a very long time until it eventually returns wrong result.
2. I assume that numbers are integers. If they are not integers, than we have infinitely many combinations and we have comparison problems.
3. We will be operating on very large numbers. 2 ^ 301 is a number with 90 digits. Hence BigInteger is the only choice. Which unfortunately will decrease performance.
4. Your current biggest problem is that you continue inner loop (increasing exponent) even if the current result is greater than x. If x = 9 then for a = 2 and b = 4 we already have 16 so we can stop increasing b and increase a instead (and reset b to 1). Your function however after checking 2 ^ 4 will check also 2 ^ 5, 2 ^ 6 and 300 more.

Here is what I came up with:

private static final int MAX_B = 300;

public String[] power2(BigInteger x) {
    increaseBase:
    for (BigInteger a = BigInteger.ONE; a.compareTo(x) <= 0; a = a.add(BigInteger.ONE)) {
        for (int b = 2; b <= MAX_B; b++) {
            BigInteger result = a.pow(b);
            if (result.equals(x)) {
                return new String[] {String.valueOf(a), String.valueOf(b)};
            }
            if (result.compareTo(x) == 1) {
                continue increaseBase;
            }
        }
    }

    return new String[] {String.valueOf(x), "1"};
}

For values below 2 billion, it is likely to be slower, however it is able to handle numbers of any size.

Further optimizations that can be done:

• increase a as long as a < roundDown(sqrt(x)) instead of until a < x
• revert the loops and start with large exponent, this will allow to modify the base by values different than 1 by checking how close to x the result was

Another idea which might be actually the most efficient one is to find prime factors of x. If we know that prime factors are 2, 2, 2, 2, 13, 13 then we can easily calculate that a = 2 * 2 * 13 and b = 2.

EDIT:

Here is the implementation of my prime factors idea. Tests and imports at the bottom.

public class PowerCalculator {

    public String[] power2(String x) {
        @SuppressWarnings("MismatchedQueryAndUpdateOfCollection") // update via increaseCountFor method
        PrimeFactorToCount primeFactorToCount = new PrimeFactorToCount();
        BigInteger number = new BigInteger(x);
        BigInteger divisor = new BigInteger("2");

        while (!number.equals(BigInteger.ONE)) {
            if (number.remainder(divisor).equals(BigInteger.ZERO)) {
                number = number.divide(divisor);
                primeFactorToCount.increaseCountFor(divisor);
            } else {
                if (gcd(primeFactorToCount.values()) == 1) {
                    return new String[] {x, "1"};
                }
                divisor = divisor.add(BigInteger.ONE);
            }
        }

        int gcd = gcd(primeFactorToCount.values());

        return primeFactorToCount.entrySet().stream()
                .map(entry -> new Exponentiation(entry.getKey(), entry.getValue()))
                .map(exponentiation -> new Exponentiation(exponentiation.base.pow(exponentiation.exponent / gcd), gcd))
                .reduce((a, b) -> new Exponentiation(a.base.multiply(b.base), gcd))
                .map(Exponentiation::asStringArray)
                .get();
    }

    private static int gcd(Collection<Integer> values) {
        return values.stream()
                .mapToLong(v -> v)
                .mapToObj(BigInteger::valueOf)
                .reduce(BigInteger::gcd)
                .map(BigInteger::intValue)
                .orElse(0);
    }

    private class Exponentiation {

        private final BigInteger base;
        private final int exponent;

        private Exponentiation(BigInteger base, int exponent) {
            this.base = base;
            this.exponent = exponent;
        }

        private String[] asStringArray() {
            return new String[] {String.valueOf(base), String.valueOf(exponent)};
        }

    }

    private class PrimeFactorToCount extends HashMap<BigInteger, Integer> {

        private void increaseCountFor(BigInteger primeFactor) {
            if (containsKey(primeFactor)) {
                put(primeFactor, get(primeFactor) + 1);
            } else {
                put(primeFactor, 1);
            }
        }

    }

}

@RunWith(Parameterized.class)
public class PowerCalculatorTest {

    private final uk.co.jpawlak.maptoobjectconverter.PowerCalculator powerCalculator = new uk.co.jpawlak.maptoobjectconverter.PowerCalculator();

    @Parameterized.Parameters(name = "{index}: returns {1} for {0}")
    public static Collection data() {
        return asList(new Object[][] {
                {input(3), expected(3, 1)},
                {input(7 * 7), expected(7, 2)},
                {input(2 * 2 * 2), expected(2, 3)},
                {input(3 * 3 * 5 * 5), expected(3 * 5, 2)},
                {input(3 * 3 * 5 * 5 * 5 * 5), expected(3 * 5 * 5, 2)},
                {input(3 * 3 * 3 * 3 * 3 * 3 * 5 * 5), expected(3 * 3 * 3 * 5, 2)},
                {input(2 * 3 * 3), expected(2 * 3 * 3, 1)},
        });
    }

    private final String input;
    private final String[] expected;

    public PowerCalculatorTest(String input, List<String> expected) {
        this.input = input;
        this.expected = expected.stream().toArray(String[]::new);
    }

    @Test
    public void test() {
        String[] actual = powerCalculator.power2(input);

        assertThat(actual, sameBeanAs(expected));
    }

    private static String input(long input) {
        return String.valueOf(input);
    }

    private static List<String> expected(long base, long exponent) {
        return ImmutableList.of(String.valueOf(base), String.valueOf(exponent));
    }

}

import com.google.common.collect.ImmutableList;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;

import java.math.BigInteger;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;

import static com.shazam.shazamcrest.MatcherAssert.assertThat;
import static com.shazam.shazamcrest.matcher.Matchers.sameBeanAs;
import static java.util.Arrays.asList;

The greatest common divisor of exponents is the final exponent of the result. If we have number 108 = 2 ^ 2 * 3 ^ 3, the final exponent can be only 1. That's why there is a check for this in the loop when we are about to check next divisor - so it "fails fast". It is also the reason while in the return statement, gcd is used as exponent. Let's have a look at number 5184:

5184 = 2^6 * 3^4 = (2^3)^2 * (3^2)^2 = 8^2 * 9^2 = (8*9)^2 = 72^2

Greatest common divisor of 6 and 4 is 2.

Further optimizations that can be done is in finding prime factors of the number. If you tried it on square of large prime number such as 100000020383 ^ 2 the loop will have to do over 1 billion iterations before it finds first prime factor. This however is completely different problem so I will not be describing it here.

Answer 2

Try this

long[] power2(long x) {
    double logX = Math.log(x);
    for (int b = 300; b > 1; --b) {
        double a = Math.exp(logX / b);
        if (Math.abs(a - Math.round(a)) < 0.0005)
            return new long[] { Math.round(a), b };
    }
    return new long[] { x, 1 };
}