Change of plans for general sum of squares
In my last post I described about Euler’s four square identity to for solving general sum of squares equation. My idea was to factorize the number, represent each prime as a sum of four squares, then use Euler’s four square identity to construct the sum of four squares representation for the original Number. But I found it slower than the algorithm I found here. So I adapted the latter. The idea is to reduce the problem of representing a number as a sum of four squares to representing a number as a sum of three squares.
Algorithm for representing a positive number n as a sum of three squares
1. If , then return
2. Write as
3. if then return the hard coded representation of . Here, . Representations for these numbers can be found here.
4. If is a perfect square then return
5. if , find an odd number such that is a prime. Set and . Find two numbers such that . (You can use Cornacchia’s algorithm for this. Return .
6. If or then find an odd number such that is a prime. Else find an even number with the above requirement. Set and . Find such that . Return .
Note that above algorithm can not be used if for some integer . That is if is in the form .
Algorithm for representing a positive number n as a sum of four squares
Every non-negative integer can be represented as a sum of four squares.
1. Write as .
2. If then set and . If or then set and . Otherwise set .
3. Use the algorithm described earlier to represent as a sum of three squares. Say, .
4. Return .
By using these two algorithms one can represent any non-negative integer as a sum of four squares. In the general sum of squares equation, where a given integer needs to be represented as a sum of squares, we can divide variables into segments of four and divide into that same number of segments and represent each segment by four squares using the algorithm given above.