"Python如何（以及为什么）精确计算完全平方的平方根"？

Question

这个 惊人 密码高尔夫答案 到 这个数字是卢埃施的吗？ 的全部内容。

Python，49字节

lambda n:0in[(n-3*i*i+0j)**.5%1for i in range(n)]

使用OEIS上给出的等效二次方程形式： n == 3*i*i+j*j. 检查是否 n-3*i*i 是一个完美的方形，适合任何 i 取其平方根并检查它是否是一个整数，即等于 0 modulo 1。请注意，Python 会精确地计算完全平方的平方根，不会出现浮点错误。 这个 +0j 使其成为一个复数，以避免负数的平方根出现错误。

Python 是如何做到这一点的？是否 **.5 以某种方式 "检测 "一个给定的数字是一个完美的平方？这是否只对整数输入可靠，还是对一定大小的浮点数也有效？

我还添加了一个括号 为什么这么说呢？ 的问题；这是程序员所依赖的东西吗？是为了速度吗？是为了成本吗？

Answer 1

你可以查看源代码 此处. 他们描述了他们用于计算非负整数的（近似）平方根的算法，并证明了对于完全平方的算法给出了准确的答案。代码是C语言，但他们给出了Python代码的翻译。

def isqrt(n):
    """
    Return the integer part of the square root of the input.
    """
    n = operator.index(n)
    if n < 0:
        raise ValueError("isqrt() argument must be nonnegative")
    if n == 0:
        return 0
    c = (n.bit_length() - 1) // 2
    a = 1
    d = 0
    for s in reversed(range(c.bit_length())):
        # Loop invariant: (a-1)**2 < (n >> 2*(c - d)) < (a+1)**2
        e = d
        d = c >> s
        a = (a << d - e - 1) + (n >> 2*c - e - d + 1) // a
    return a - (a*a > n)

我假设，但还没有检查过，当在运行时计算一个幂时，Python首先检查： 1. 基数是一个非负整数， 2. 0.5如果这两个都成立，那么它就会调用我上面链接的代码。