如何找到整数第n个根？

Question

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

int(n**(1/k))

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

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

什么是更好的算法？

---

背景:2011年,这次失误让我击败Google Code Jam.https://code.google.com/codejam/contest/dashboard?c=1150486#s=p2

Answer 1

怎么样:

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.

Answer 2

一个解决方案首先将lo和hi之间的答案括起来,重复乘以2直到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