Finding perfect powers

Testing whether an integer n is a perfect power is a question of finding integers x and k (k >= 2) such that x ^ k == n.

Finding x and k (or else discovering that they don't exist) can be done efficiently in a couple different ways. One way (which I'm using in this repo) is, given a value of k, do a binary search on possible values of x that result in x ^ k == n. Suppose we want to know if n is a perfect square (k == 2). So try setting x = 2 ^ (log n / 2) and see if x ^ 2 == n. If so, great, we're done. Otherwise, if the squared result is less than n, add 2 ^ ((log n / 2) - 1) to x and iterate, else, if the squared result is greater than n, set x = 2 ^ ((log n / 2) - 1) and iterate. Basically you conditionally add in decreasing powers of 2 to x to try to get something that, when squared, is n.

For other values of k we do a similar binary search, except starting at a smaller initial value (eg 2 ^ (log (n / 4)) for k == 4).

So that's the basic idea for one value of k. The other detail is how many possible values of k there can be, but fortunately the answer is no more than O(log n), since 2 ^ ((log n) + 1) > n, and 2 is the smallest possible value for x. So the overall timing is O((log n) ^ 4), assuming exponentiation takes time O((log n) ^ 3) time, which makes this test perfectly reasonable to use when trying to factor a number.

Another way of finding a root of n is Newton's method: https://en.wikipedia.org/wiki/Newton%27s_method It is asymptotically the same as binary search but seems to be faster in practice, but I'm less familiar with it so I haven't tried implementing it yet.