将给定数字表示为两个平方和的算法

Question

我的问题如下：

我有一个自然数 n，我想找到所有自然数 x 和 y 使得

n = x² + y²

由于这是加法顺序无关紧要所以我将 (x,y) 和 (y,x) 算作一个解决方案。

我的初始算法是假设 y>x，对于所有 x 计算 y²=n-x² 并使用对 y² 的二进制搜索检查 y 是否是自然数。


for(x=1;2*x*x<n;x++)
{
     y_squared=n-x*x;
     if(isSquare(y_squared)==false)
           continue;

     //rest of the code
}

我的算法有什么改进吗？我已经检查过 n 是否可以使用两个平方定理有解，但我想知道有多少个。

我的算法是 O(sqrt(n) * log(n) )

提前致谢。

Answer 1

您可以这样将其减少到 O(sqrt(n))：

all_solutions(n):
    x = 0
    y = floor(sqrt(n))

    while x <= y
        if x * x + y * y < n
            x++
        else if x * x + y * y > n
            y--
        else
            // found a match
            print(x, y)
            x++
            y--

此算法将查找并打印所有可能的解决方案，并且将始终终止 x <= sqrt(n / 2) 和 y >= sqrt(n / 2)，导致最多执行 sqrt(n / 2) + (sqrt(n) - sqrt(n / 2)) = sqrt(n) 次迭代。

Answer 2

的变体，跟踪平方和并仅使用 additions/subtractions 进行调整：

伪代码：（从左到右计算 x++ + x 和 y-- + y，或者像 Python 代码那样下）

x = 0
y = floor(sqrt(n))
sum = y * y

while x <= y
    if sum < n
        sum += x++ + x
    else if sum > n
        sum -= y-- + y
    else
        print(x, y)
        sum += 2 * (++x - y--)

Java:

  static void allSolutions(int n) {
    int x = 0, y = (int) Math.sqrt(n), sum = y * y;
    while (x <= y) {
      if (sum < n) {
        sum += x++ + x;
      } else if (sum > n) {
        sum -= y-- + y;
      } else {
        System.out.println(x + " " + y);
        sum += 2 * (++x - y--);
      }
    }
  }

Python:

from math import isqrt

def all_solutions(n):
    x = 0
    y = isqrt(n)
    sum = y ** 2

    while x <= y:
        if sum < n:
            x += 1
            sum += 2 * x - 1
        elif sum > n:
            sum -= 2 * y - 1
            y -= 1
        else:
            # found a match
            print(x, y)
            x += 1
            sum += 2 * (x - y)
            y -= 1

演示：

>>> all_solutions(5525)
7 74
14 73
22 71
25 70
41 62
50 55

将给定数字表示为两个平方和的算法

Algorithm for expressing given number as a sum of two squares

algorithm

optimization

mathematical-optimization