如何找到整数n次根？

Question

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

int(n**(1/k))

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

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

什么是更好的算法？

背景：在 2011 年，这个失误让我击败了 Google Code Jam 问题 Expensive Dinner 。

原文由 Colonel Panic 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

原文由 user448810 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 都应该是正整数。这使得 return 表达式完全依赖整数运算，消除了舍入错误的任何可能性。

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

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

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

int() 将其截断为 4 。

原文由 NPE 发布，翻译遵循 CC BY-SA 3.0 许可协议