Representing an integer as the sum of four squares

Given a positive integer m, find four integers a, b, c, 开发者_开发百科d such that a^2 + b^2 + c^2 + d^2 = m in O(m^2 log m). Extra space can be used.

I can think of an O(m^3) solution, but I am confused about the O(m^2 logm) solution..

---

First hint:

What is the complexity of sorting squared elemnt from 1 to m^2

Second hint:

Have a look at this post for some help :

Break time, find any triple which matches pythagoras equation in O(n^2)

Third Hint:

If you need more help : (from yi_H response on the previous post):

I guess O(n^2 log n) would be to sort the numbers, take any two pairs (O(n^2)) and see whether there is c in the number for which c^2 = a^2 + b^2. You can do the lookup for c with binary search, that's O(log(n)).

author: yi_H

Now compare n and sqrt(m)

Hope you can figure out a solution with this.

---

There is a classical theorem of Lagrange that says that every natural number is the sum of four squares.

The Wikipedia page on this topic mentions that there is a randomized algorithm for computing the representation that runs in O(\lg^2 m) time (all the suggestions above are polynomial in m, i.e., they are exponential in the size of the problem instance (since the number m can be encoded in \lg m bits).

As an aside, Lagrange's theorem proves the undecidability of the integers with plus and times (since the naturals are undecidable, and can be defined in the integers with plus and times, by virtue of the theorem).