An efficient algorithm to represent a number as sum of $4$ squares I need to find any one of all the possible square quadruples that sum to a given number. The number can be as large as $10^{12}$.
I have tried a $o(n)$ complexity algorithm but that is not sufficient to calculate within the time limit.
 A: For some weird reason, I cannot make comments due to low reputation, so I'm forced to write this comment as answer.
You need to make clear if you are searching integer solutions. Otherwise, your solution is trivial $n=x^2+x^2+x^2+x^2 \to x=\sqrt{\frac{n}{4}}$
Anyways, if you are searching integer solutions, should all be different numbers, or can they be repeated? 
Is 0 allowed as solution?
If only integers larger than 0 without repetition are allowed, the worst algorithm cannot be larger than $o(\sqrt{n})$
Do you need a fast algorithm on average, or for every run? A greedy algorithm running in parallel would reduce your average time.
This is a greedy algorithm:
$n=a^2+b^2+c^2+d^2$
Assume $a\geq b\geq c\geq d \geq 1$
The largest possible values for a, b, c, d are:
$a= truncate(\sqrt{n-3})=\lfloor \sqrt{n-3} \rfloor$
$b=\lfloor \sqrt{n-a^2-2} \rfloor$
$c=\lfloor \sqrt{n-a^2-b^2-1} \rfloor$
$d=\lfloor \sqrt{n-a^2-b^2-c^2} \rfloor$
It is either the solution, or you get a remaining r:
$r=n-(a^2+b^2+c^2+d^2)$
If r>0 then you have up to 4 integer errors $e_i \in \mathbb{Z}$
$n=(a+e_a)^2+(b+e_b)^2+(c+e_c)^2+(d+e_d)^2$
$r=e_a^2+e_b^2+e_c^2+e_d^2+2.(a.e_a+b.e_b+c.e_c+d.e_d)$
But because n is large, $e_a<<e_b<<e_c<<e_d$, with a high probability of $e_a=0$, $e_b=0$, so assume $e_a=e_b=e_c=0$ and solve for $r=e_d^2+2.(d.e_d)$
if $e_d$ is not an integer, solve for
$e_a=e_b=0$
$r=e_c^2+e_d^2+2.(c.e_c+d.e_d)$
$c+e_c \geq d+e_d$ (because c>d by definition)
$e_c<0$
$e_d>0$
At this point, you will most probably have found a solution. Otherwise assume that only $e_a=0$, and solve the other errors.
In the worst case, $e_a \neq 0$, but at least you know that $e_a<0$, and $a+e_a \geq b+e_b \geq c+e_c \geq d+e_d$
