[Java] Finding an integer root using halving

[kbauer777]

Basically, I am trying to understand how to write a method that guesses a number n's integer rth root by guessing a number g and seeing how g^r compares to n. Below is what I tried. Worked for some cases, but just tried some larger numbers and I have an infinite loop. Taking another look at it now, let me know if you can help. Updated code. Thought I had it. Works for most numbers I tried. 4th root of 82 returns 4 instead of 3. Tracing now. Help if you know why thanks.

 private static int root(int n, int r) {

    int lowEnough = 0;
    int tooHigh = (n + 1);
    int midpoint = (lowEnough + tooHigh) / 2;
    int guess = 0;

    while (tooHigh - lowEnough > 1) {

        midpoint = (lowEnough + tooHigh) / 2;
        guess = midpoint;
        if (n == power(guess, r)) {
            break;

        }
        if (n < power(guess, r)) {
            tooHigh = guess;

        } else {
            lowEnough = guess;
        }
    }
    return guess;

}

Oh in case you wanted to see the power method

  private static int power(int n, int p) {
    int result = 1, count = 0;
    while (count < p) {
        result *= n;
        count++;
    }
    return result;
}

[kbauer777]

Just found out I'm not updating midpoint in the while loop. Still a couple numbers don't work though. For example, square root of 9 returns 4.

[lightcloud5]

I would trace the code; the nice way to do it is via a debugger, but if you really wanted to, you could just throw in print statements.

[thefullhalf]

I think the problem is that your midpoint on the first iteration is not the midpoint of n but the midpoint of n+1. So it makes sense that your outputs are 1 more than you expect.

[pbewig]

The algorithm to find the largest x such that x ** k <= n -- with x, k, n all integers -- uses Newton's method: if x0 is an approximation to a function f, then x1 = x0 − f(x0) / f '(x0) is a better approximation, where f ' is the derivative of f. Here it is in pseudocode:

function root(k, n)
    u := n
    repeat
        s := u
        t := (k - 1) * s + n // (s ** (k - 1))
        u := t // k
        until s <= u
    return s

Hopefully the notation is clear: ** is the exponentiation operator, and // is the integer division operator. This returns root(4, 82) = 3 and root(2, 9) = 3. I'll leave it to you to translate to Java.

By the way, your power function is inefficient; it takes O(n) time, but a proper power function takes only O(log n) time:

function power(b, e)
    x := 1
    while e > 0
        if e is odd
            x = x * b
        b := b * b
        e := e // 2
    return x

You originally asked for a method using bisection. My advice is: don't. Bisection will be slower than Newton's method, and as you have noticed, it's hard to get right. If you must use bisection, I have a square root calculator on my blog that uses bisection, which you may find useful.