Tell me more ×  A question was asked at Stack Overflow (here):
Given an integer $N$, print out all possible combinations of
integer values of $A,B,C$ and $D$ which solve the equation
$A^2+B^2+C^2+D^2 = N$.  This question is of course related to
Bachet's Conjecture in number theory (sometimes called
Lagrange's Four Square Theorem because of his proof). There are
some papers that discuss how to find a single solution, but I
have been unable to find anything that talks about how fast we
can find all solutions for a particular $N$ (that is, all
combinations, not all permutations).  I have been thinking about
it quite a bit and it seems to me that it can be solved in
$O(N)$ time and space, where $N$ is the desired sum. However,
lacking any prior information on the subject, I am not sure if
that is a significant claim on my part or just a trivial,
obvious or already known result.  So, the question then is, how
fast can we find all of the Four-Square Sums for a given $N$?
OK, here's the (nearly) O(N) algorithm tha