Python 如何找到整数n次根？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15978781/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to find integer nth roots?
提问by Colonel Panic
I want to find the greatest integer less than or equal to the kth root of n. I tried
我想找到小于或等于 n 的第 k 个根的最大整数。我试过
int(n**(1/k))
But for n=125, k=3 this gives the wrong answer! I happen to know that 5 cubed is 125.
但是对于 n=125, k=3 这给出了错误的答案！我碰巧知道 5 的立方是 125。
>>> int(125**(1/3))
4
What's a better algorithm?
什么是更好的算法？
Background: In 2011, this slip-up cost me beating Google Code Jam. https://code.google.com/codejam/contest/dashboard?c=1150486#s=p2
背景：2011 年，这个失误让我击败了 Google Code Jam。https://code.google.com/codejam/contest/dashboard?c=1150486#s=p2
采纳答案by user448810
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:
一种解决方案首先通过重复将 hi 乘以 2 直到 n 介于 lo 和 hi 之间来将 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
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
回答by NPE
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 valand nare expected to be integer and positive. This makes the returnexpression rely exclusively on integer arithmetic, eliminating any possibility of rounding errors.
在这里，val和n都应该是整数和正数。这使得return表达式完全依赖于整数算术，消除了任何舍入错误的可能性。
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).
请注意，只有在val**(1./n)相当小时才能保证精度。一旦该表达式的结果与真实答案的偏差超过1，该方法将不再给出正确答案（它将给出与原始版本相同的近似答案）。
Still I am wondering why
int(125**(1/3))is4
不过我很奇怪，为什么
int(125**(1/3))是4
In [1]: '%.20f' % 125**(1./3)
Out[1]: '4.99999999999999911182'
int()truncates that to 4.
int()将其截断为4.
回答by Stochastically
int(125**(1/3))should clearly be 5, i.e. the right answer, so this must be standard computer rounding error, i.e internally the result is 4.9999999999 which gets rounded down to 4. This problem will exist with whatever algorithm you use. One simple ad-hoc solution is to add a tiny number e.g. int((125**(1/3)) + 0.00000001)
int(125**(1/3))显然应该是 5，即正确答案，所以这必须是标准的计算机舍入误差，即内部结果是 4.9999999999，它被舍入为 4。无论您使用什么算法，都会存在这个问题。一个简单的临时解决方案是添加一个小数字，例如int((125**(1/3)) + 0.00000001)
回答by Alexandre C.
You can round to nearest integer instead of rounding down / to zero (I don't know what Python specifies) :
您可以四舍五入到最接近的整数而不是向下舍入到零（我不知道 Python 指定了什么）：
def rtn (x):
return int (x + 0.5)
>>> rtn (125 ** (1/3))
5
回答by Doug Currie
Here it is in Lua using Newton-Raphson method
这是在 Lua 中使用 Newton-Raphson 方法
> function nthroot (x, n) local r = 1; for i = 1, 16 do r = (((n - 1) * r) + x / (r ^ (n - 1))) / n end return r end
> return nthroot(125,3)
5
>
Python version
蟒蛇版
>>> def nthroot (x, n):
... r = 1
... for i in range(16):
... r = (((n - 1) * r) + x / (r ** (n - 1))) / n
... return r
...
>>> nthroot(125,3)
5
>>>
回答by khan
Do this before everything:
在一切之前这样做：
from __future__ import division
and then run any of the above specified techniques to have your results.
然后运行任何上述指定的技术以获得您的结果。
回答by Colonel Panic
My cautious solution after being so badly burned:
被严重烧伤后我谨慎的解决方案：
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
回答by Escualo
I wonder if starting off with a method based on logarithms can help pin down the sources of rounding error. For example:
我想知道从基于对数的方法开始是否有助于确定舍入误差的来源。例如：
import math
def power_floor(n, k):
return int(math.exp(1.0 / k * math.log(n)))
def nth_root(val, n):
ret = int(val**(1./n))
return ret + 1 if (ret + 1) ** n == val else ret
cases = [
(124, 3),
(125, 3),
(126, 3),
(1, 100),
]
for n, k in cases:
print "{0:d} vs {1:d}".format(nth_root(n, k), power_floor(n, k))
prints out
打印出来
4 vs 4
5 vs 5
5 vs 5
1 vs 1
回答by ecline6
def nth_root(n, k):
x = n**(1./k)
y = int(x)
return y + 1 if y != x else y
回答by Natig Aliyev
Why not to try this :
为什么不试试这个：
125 ** (1 / float(3))
or
或者
pow(125, 1 / float(3))
It returns 5.0, so you can use int(), to convert to int.
它返回 5.0，因此您可以使用 int() 转换为 int。
