[Java] Calculate nth root

Given a number, calculate the nth root within a certain precision epsilon.

Without using square functions, we need to approximate the result ourselves.

We could start from epsilon, calculate the nth power of it, then verify whether it differs from the given number by at most the given epsilon.

If yes, we have our result, otherwise, we increase our start value by epsilon and repeat.

This can be done iteratively in constant space but has a terrible time complexity O(all possible numbers between epsilon and N with precision epsilon).

We can improve on this by using binary search as in the end we're looking for a value within a range.

We set our floor to 0 and our ceil to N, then our mid point is at each time the candidate for our nth root.

We multiply mid with itself to calculate the nth power, and verify if we're within epsilon of the given number, which means we have found the root.

If not, we check whether we overshot or undershot and set ceil or floor respectively to mid. We do NOT use mid plus or minus something since we're dealing with doubles and any fluctuation might lead to a wrong result.

Additionally mid is the midpoint between floor and ceil, and since we're dealing with floating point values it's guaranteed it will never be equal to either bound (unless we have reached the minimum possible precision of the double type).

The complexity now is O(log all possible numbers between 0 and N with precision epsilon) which is much better than before.

Space complexity stays the same since we're doing the iterative approach.

You can check my implementation of nRoot on my Gist along with some tests in NRootJTests.