I am trying to search for integer solutions to the equation:
y^2 + x^2 = 2n^2
If I search this in wolfram alpha, they are all found almost immediately even for very large n. When I implemented a brute force approach it was very slow:
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
So I assume there is a much faster way to get all of the integer solutions to the equation above. How can I do this in python so that it will have much lower runtime?
Note: I have seen this question however it is about finding lattice points within a circle not the integer solutions to the equation of the circle. Also I am interested in finding the specific solutions not just the number of solutions.
Edit: I am still looking for something an order of magnitude faster. Here is an example: n=5 should have 12 integer solutions to find what those should be search this equation on Wolfram alpha.
Edit 2: @victor zen gave a phenomenal answer to the problem. Can anyone think of a way to optimize his solution further?
Advertisement
Answer
In your algorithm, you’re searching for all possible y values. This is unnecessary. The trick here is to realize that
y^2 + x^2 = 2n^2
directly implies that
y^2 = 2n^2-x^2
so that means you only have to check that 2n^2-x^2 is a perfect square. You can do that by
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.
Also, in your algorithm, you are only checking x values up to n. This is incorrect. Since y^2 will always be positive or zero, we can determine the highest x value we need to check by setting y^2 to its lowest value (i.e 0). Consequentially, we need to check all integer x values satisfying
x^2 <= 2n^2
which reduces to
abs(x) <= sqrt(2)*n.
Combine this with the optimization of only checking the top quadrant, and you have an optimized psearch of
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