5 of 9 added 3 characters in body

# CJam, 90 bytes / GolfScript, 98 bytes

q~_4096:R%{1}{R/64}?:R;_zmqi)257:B_**__{;;(_[{_B%\B/}2*]_{_*}/++3$\-_zmqi__*@-}g+]2={R*}%  or ~.4096:r%{1}{r/64}if:r;{..*4-1??n*,}:v~)257:b.**.. {;;(.[{.b%\b/}2*].{.*}/++3$\-v..*@-}do+]2={r*}%


Compact, but slower than my other approach. The newline can be removed.

You can try the CJam solution online. Paste the Code, type the desired integer in Input and click Run.

### Background

The algorithm computes the numbers by brute force:

1. If n is a multiple of 4096, set n = n / 4096.

2. Set i = 257**2 * floor(sqrt(n)) + 257 * 256 + 256.

3. Find integers j, k, l such that i = 257**2 * j + 257 * k + l, where k, l < 257.

4. Check if n - j**2 - k**2 - l**2 is a perfect square.

5. If it isn't, set i = i - 1 and go back to step 3.

### Examples

$TIME='\n%e s' time cjam lagrange.cjam <<< 999999999 [15 221 31622 7] 0.32 s$ TIME='\n%e s' time cjam lagrange.cjam <<< 805306368
[8192 8192 24576 8192]
4.75 s
 TIME='%e s' time golfscript lagrange.gs <<< 999999999
[15 221 31622 7]
0.46 s
$TIME='%e s' time golfscript lagrange.gs <<< 805306368 [8192 8192 24576 8192] 140.30 s  Timings correspond to an Intel Core i7-4700MQ. The worst case is still under the three minute limit with GolfScript; it takes less than 5 seconds with CJam. ### How it works q~ " Read and interpret the input. Result: “n” (non-negative integer) "; _4096:R% " Check if “n” is divisible by 4096. "; {1}{R/64}?:R; " If it is, set n = n / 4096 and R = 8; otherwise, set R = 1. "; _zmqi " Compute the integer part of the square root of |n|. "; )257:B_** " Compute i = (n + 1) * 257**2. "; __ " Duplicate “i” twice (dummy values). "; { " "; ;;(_ " Discard two items from the stack and increment “i”. "; [{_B%\B/}2*] " Push [ j k l ], where i = 257**2 * j + 257 * k + l and k, l < 257. "; _{_*}/++ " Compute j**2 + k**2 + l**2. "; 3$\-          " Compute m = n - (j**2 + k**2 + l**2). ";
_zmqi         " Compute the integer part of the square root of |m|. ";
__*@-         " Square the result, rotate “m” on top of it and subtract. ";
}g              " If the result is 0 “m” is a perfect square; break the loop. ";
+]2=            " Push “m” on [ j k l ] and discard everything except [ j k l m ]. ";
{R*}%           " Push [ Rj Rk Rl Rm ]. ";
               " Convert the result into a string. ";


The only real difference between this code above and the GolfScript version of it is that GolfScript requires implementing a function to substitute zqmi`. I have explained in my other answer how this is achieved.