几年前，我写过一篇关于快速测试整数n是否为平方数的文章。该算法根据整数的最后一位（十六进制）数字，排除一些不能为平方数的数字。如果整数通过了初步筛选，算法会将n的平方根取为浮点数，四舍五入为整数，然后测试余数的平方是否等于n 。
旧算法有什么问题
如果n不是太大，上述算法可以正常工作。然而，它隐式地假设该整数可以精确地表示为浮点数。这有两个假设：(1) 它不是太大而无法表示；(2) 表示是精确的。
标准的 64 位浮点数有 1 位符号位、11 位指数位和 52 位有效位。（更多信息请见此处。）如果指数位用完，数字就会溢出；如果有效位用完，数字就会失去精度。例如，2 1024就会溢出 [1]。虽然 2 53 + 1 不会溢出，但它无法精确表示。
下面用 Python 对此进行了说明。
>>> 浮点数（2**1024） OverflowError：int 太大，无法转换为 float >>> n = 2**53 >>> float(n) == float(n + 1) 真的
更好的算法
以下算法 [2] 仅使用整数运算，因此在 Python 中它可以精确处理任意大的整数。它是牛顿平方根算法的离散模拟。
定义 intsqrt（N）： n = N 当 n**2 > N 时： n = (n + N//n) // 2 返回 n 定义 issquare（N）： n = intsqrt(N) 返回 n**2 == N
函数issquare可以测试N是否为平方数。函数intsqrt被拆分成一个单独的函数，因为它返回 ⌊√ N ⌋，具有独立用途。
上述代码正确处理了原始算法无法处理的示例。
>>> issquare(2**1024) 真的 >>> issquare(2**54) 真的 >>> issquare(2**54 + 1) 错误的
您可以通过快速返回False来加快issquare速度，因为对于由于其最后一位数字而无法平方的数字（在某些进制中 – 也许您想使用大于 16 的进制），就像在原始帖子中一样。
[1] 允许的最大指数为 1023，原因请见此处。
[2] Bob Johnson. 《寻根之路》。《数学公报》，第 74 卷，第 469 期（1990 年 10 月），第 284-285 页
测试一个大整数是否为平方数一文最先出现在John D. Cook身上。
原文： https://www.johndcook.com/blog/2025/06/26/large-integer-square/