python - 圆的整数解算法？

Question

我正在尝试搜索方程的整数解:

y^2 + x^2 = 2n^2

如果我在 wolfram alpha 中搜索它，即使对于非常大的 n，也几乎可以立即找到它们。当我实现蛮力方法时，它非常慢:

def psearch(n, count):
    for x in range(0, n):
        for y in range(0, n):
            if x*x + y*y == 2*n**2:
                print(x,y)
                count += 1
    return count

所以我假设有一种更快的方法来获得上述方程的所有整数解。我如何在 python 中执行此操作，以便运行时间更短？

注:我看过this question然而，它是关于在 圆内找到格点，而不是圆方程的整数解。此外，我有兴趣找到特定的解决方案而不仅仅是解决方案的数量。

编辑:我仍在寻找更快一个数量级的东西。这是一个例子:n=5 应该有 12 个整数解来找到那些应该在 Wolfram alpha 上搜索这个等式.

编辑 2:@victor zen 对这个问题给出了非凡的答案。谁能想办法进一步优化他的解决方案？

Answer 1

在您的算法中，您正在搜索所有可能的 y 值。这是不必要的。这里的技巧是要意识到这一点

y^2 + x^2 = 2n^2

直接暗示

y^2 = 2n^2-x^2

所以这意味着你只需要检查 2n^2-x^2 是一个完美的正方形。你可以通过

y2 = 2*n*n - x*x 
#check for perfect square
y = math.sqrt(y2)
if int(y + 0.5) ** 2 == y2:
    #We have a perfect square.

此外，在您的算法中，您只检查 x 到 n 的值。这是不正确的。由于 y^2 总是正数或零，我们可以通过将 y^2 设置为其最低值(即 0)来确定我们需要检查的最高 x 值。因此，我们需要检查所有满足

x^2 <= 2n^2

减少到

abs(x) <= sqrt(2)*n.

将此与仅检查顶部象限的优化相结合，您将获得优化的 psearch

def psearch(n):
    count = 0
    top = math.ceil(math.sqrt(2*n*n))
    for x in range(1, top):
        y2 = 2*n*n - x*x 
        #check for perfect square
        y = math.sqrt(y2)
        if int(y + 0.5) ** 2 == y2:
            count+=4
    return count