python中的整数平方根

本文介绍了python中的整数平方根的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

python或标准库中是否存在整数平方根？我希望它是精确的（即返回一个整数），并且如果没有解决方案则吠叫。

Is there an integer square root somewhere in python, or in standard libraries? I want it to be exact (i.e. return an integer), and bark if there's no solution.

目前我推出了自己的天真产品：

At the moment I rolled my own naive one:

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中......

But it's ugly and I don't really trust it for large integers. I could iterate through the squares and give up if I've exceeded the value, but I assume it would be kinda slow to do something like that. Also I guess I'd probably be reinventing the wheel, something like this must surely exist in python already...

推荐答案

Newton's方法在整数上运行得非常好：

Newton's method works perfectly well on integers:

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

这将返回 x * x 不超过 n的最大整数 x 。如果你想检查结果是否正好是平方根，只需执行乘法检查 n 是否是一个完美的正方形。

This returns the largest integer x for which x * x does not exceed n. If you want to check if the result is exactly the square root, simply perform the multiplication to check if n is a perfect square.

I在我的博客中讨论此算法以及其他三种计算平方根的算法。

I discuss this algorithm, and three other algorithms for calculating square roots, at my blog.