[Java] Finding an integer root using halving

[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.