Algorithm for expressing given number as a sum of two squares

Question

My problem is as follows:

I'm given a natural number n and I want to find all natural numbers x and y such that

n = x² + y²

Since this is addition order does not matter so I count (x,y) and (y,x) as one solution.

My initial algorithm is to assume that y>x, for all x compute y²=n-x² and check if y is a natural number using binary search on y².

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

     //rest of the code
}

Is there any improvement for my algorithm? I already checked if n can have solutions using two squares theorem, but I want to know how many there are.

My algorithm is O(sqrt(n) * log(n) )

Thanks in advance.

Answer 1

You can reduce this to O(sqrt(n)) this way:

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

This algorithm will find and print all possible solutions and will always terminate for x <= sqrt(n / 2) and y >= sqrt(n / 2), leading to at most sqrt(n / 2) + (sqrt(n) - sqrt(n / 2)) = sqrt(n) iterations being performed.