Algorithm for solving equation: x^2 - 4y^2 = n

Question

Lately, I was participating in a job interview, that included programming assignments. One of the assignments was:
White a function, that will find all integer values pairs x, y that for given integer n solve the equation: x^2 - 4y^2 = n

My approach was: I rewrote thes equation for y: y = sqrt(x^2 - n) / 2
Made for loop from x=sqrt(n) to x=n
For every x I computed y value and checked, if y is an integer.

This solution gave corrected answers, however, for large n this algorithm did not meet performance criteria.
In assignment there were also hint given, that: x^2 - 4y^2 = (x - 2y)(x + 2y), but I have no idea how to use this hint for solving that problem.

Just for curiosity (as the assignment is now over), any ideas how to solve this problem in an optimal way?

Answer 1

The hint x^2 - 4y^2 = (x - 2y)(x + 2y) means that n must be divisible by (x - 2y) and (x + 2y). So, for example an integer factorization of n yields a relatively small set of integers that can be searched for whether they can produce numbers of the form (x - 2y) and (x + 2y).

It suffices to consider positive integers x and y because due the squares in the equation, for every x also -x is a solution and the same holds for y. So every pair of numbers you find actually gives you four different solutions.

---

You may also want to check out the theory of Diophantine equations, which is the general mathematical theory behind this kind of problem. Your special case is adressed in a MathWorld article.

Answer 2

In your approach you end up doing a loop from sqrt(n) to n. Which means the time complexity of your solution is O(n).

If we were interested in negative solutions we could, given a non-negative pair (x, y) create the 3 solutions, (-x, y), (x, -y) and (-x, -y) (these solutions are not necessarily distinct since x or y can be 0). So we can restrict ourselves to non-negative x and y. I am also assuming n > 0.

Now suppose a = x - 2y and b = x + 2y. With a <= b because y >= 0.

Then a * b = n and b = n / a.

We can now loop through all values of a with 1 <= a <= sqrt(n) and check if b = n / a is an integer. (If a were larger than sqrt(n), b = n / a would be smaller than a.)

For all values of a where b is an integer we calculate x = (a + b) / 2 and y = (b - a) / 4. If x and y are integers, we have a solution.

The time complexity of this algorithm is O(sqrt(n)).