如何找到整数n根？

Question

我想找到小于或等于n的第k个根的最大整数

int(n**(1/k))

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

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

什么是更好的算法？

背景：2011年，这个失误让我打败了谷歌代码堵塞。https://code.google.com/codejam/contest/dashboard?c=1150486#s=p2

Answer 1

我被严重烧伤后的谨慎解决方案：

def nth_root(N,k):
    """Return greatest integer x such that x**k <= N"""
    x = int(N**(1/k))      
    while (x+1)**k <= N:
        x += 1
    while x**k > N:
        x -= 1
    return x

Answer 2

怎么样：

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)

这里，val和n都应该是整数和正数。这使得返回表达式完全依赖于整数算术，消除了舍入错误的任何可能性。

请注意，只有当val**（1./n）相当小时，才能保证准确性。一旦该表达式的结果偏离真实答案超过1，该方法将不再给出正确答案（它将给出与原始版本相同的近似答案）。

我仍然想知道为什么int（125**（1/3））是4

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

int（）将其截断为4。

Answer 3

一种解决方案首先通过重复将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