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.