如何求整数n次根？

我想找到小于或等于n的k次方根的最大整数。我试过

int(n**(1/k))

但对于 n=125，k=3，这给出了错误的答案！我碰巧知道 5 的立方是 125。

>>> int(125**(1/3))
4

有什么更好的算法？

背景：2011 年，这个失误让我在 Google Code Jam 问题上失败了昂贵的晚餐 https://codingcompetitions.withgoogle.com/codejam/round/0000000000432f3b/0000000000432b31.

一种解决方案首先通过将 hi 重复乘以 2 将答案括在 lo 和 hi 之间，直到 n 介于 lo 和 hi 之间，然后使用二分查找来计算确切的答案：

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

另一种解决方案使用牛顿法，该方法在整数上效果非常好：

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