python中的整数平方根

威姆:

在python或标准库中的某个地方是否存在整数平方根?我希望它是精确的(即返回一个整数),如果没有解决办法,可以吠叫。

此刻,我滚动了自己的幼稚:

def isqrt(n):
    i = int(math.sqrt(n) + 0.5)
    if i**2 == n:
        return i
    raise ValueError('input was not a perfect square')

但这很丑陋,我真的不相信大整数。我可以遍历正方形,如果超出了该值,则放弃,但是我认为做这样的事情有点慢。另外我想我可能正在重新发明轮子,类似这样的东西肯定已经存在于python中了...

用户448810:

牛顿的方法在整数上工作得很好:

def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

这将返回的最大整数X为其中X * X不超过ñ如果要检查结果是否恰好是平方根,只需执行乘法以检查n是否为理想平方。

我在博客上讨论了该算法以及其他三种用于计算平方根的算法

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章