How to find integer nth roots?

How about:

def nth_root(val, n):
    ret = int(val**(1./n))
    return ret + 1 if (ret + 1) ** n == val else ret

print nth_root(124, 3)
print nth_root(125, 3)
print nth_root(126, 3)
print nth_root(1, 100)

Here, both val and n are expected to be integer and positive. This makes the return expression rely exclusively on integer arithmetic, eliminating any possibility of rounding errors.

Note that accuracy is only guaranteed when val**(1./n) is fairly small. Once the result of that expression deviates from the true answer by more than 1, the method will no longer give the correct answer (it'll give the same approximate answer as your original version).

Still I am wondering why int(125**(1/3)) is 4

In [1]: '%.20f' % 125**(1./3)
Out[1]: '4.99999999999999911182'

int() truncates that to 4.

One solution first brackets the answer between lo and hi by repeatedly multiplying hi by 2 until n is between lo and hi, then uses binary search to compute the exact answer:

def iroot(k, n):
    hi = 1
    while pow(hi, k) < n:
        hi *= 2
    lo = hi // 2
    while hi - lo > 1:
        mid = (lo + hi) // 2
        midToK = pow(mid, k)
        if midToK < n:
            lo = mid
        elif n < midToK:
            hi = mid
        else:
            return mid
    if pow(hi, k) == n:
        return hi
    else:
        return lo

A different solution uses Newton's method, which works perfectly well on integers:

def iroot(k, n):
    u, s = n, n+1
    while u < s:
        s = u
        t = (k-1) * s + n // pow(s, k-1)
        u = t // k
    return s