Sum of two squares in Python-CodePudding

I have written a code based on the two pointer algorithm to find the sum of two squares. My problem is that I run into a memory error when running this code for an input n=55555**2 66666**2. I am wondering how to correct this memory error.

def sum_of_two_squares(n):
    look=tuple(range(n))
    i=0
    j = len(look)-1
    while i < j:
        x = (look[i])**2   (look[j])**2
        if x == n:
            return (j,i)
        elif x < n:
            i  = 1
        else:
            j -= 1
    return None

n=55555**2   66666**2
print(sum_of_two_squares(n))

The problem Im trying to solve using two pointer algorithm is: return a tuple of two positive integers whose squares add up to n, or return None if the integer n cannot be so expressed as a sum of two squares. The returned tuple must present the larger of its two numbers first. Furthermore, if some integer can be expressed as a sum of two squares in several ways, return the breakdown that maximizes the larger number. For example, the integer 85 allows two such representations 7*7 6*6 and 9*9 2*2, of which this function must therefore return (9, 2).

CodePudding user response：

You're creating a tuple of size 55555^2 66666^2 = 7530713581

So if each element of the tuple takes one byte, the tuple will take up 7.01 GiB.

You'll need to either reduce the size of the tuple, or possibly make each element take up less space by specifying the type of each element: I would suggest looking into Numpy for the latter.

Specifically for this problem:

Why use a tuple at all?

You create the variable look which is just a list of integers:

look=tuple(range(n))  # = (0, 1, 2, ..., n-1)

Then you reference it, but never modify it. So: look[i] == i and look[j] == j.

So you're looking up numbers in a list of numbers. Why look them up? Why not just use i in place of look[i] and remove look altogether?

CodePudding user response：

You do not need the ranges at all, and certainly do not need to convert them into tuples. They take a ridiculous amount of space, but you only need their current elements, numbers i and j. Also, as the friendly commenter suggested, you can start with sqrt(n) to improve the performance further.

def sum_of_two_squares(n):
    i = 1
    j = int(n ** 1/2)

    while i < j:
        x = i * i   j * j
        if x == n:
            return j, i

        if x < n:
            i  = 1
        else:
            j -= 1

Bear in mind that the problem takes a very long time to be solved. Be patient. And no, NumPy won't help. There is nothing here to vectorize.