#include <assert.h>
#include <math.h>
#include "Recursion.h"

/* Mathematical fact:  every positive integer 
can be written as the sum of four perfect squares.
*/
/* 5 = 2^2 + 1^2 + 0^2 + 0^2
   6  = 2^2 + 1^2 + 1^2 + 0^2
   7  = 2^2 + 1^2 + 1^2 + 1^2
   8 = 2^2 + 2^2
*/

int NaiveFourSquares(long long n,int *a, int *b, int *c, int *d)
// find (if possible) four integers p,q,r,s such that 
// p <= q <= r <= s and 
// p^2 + q^2 + r^2 + s^2 == n, and write them into *a, *b, *c, *d
// respectively.  
// Return 0 for success or -1 if no such p,q,r,s exist.
  
{  int p,q,r,s;
   int B = (int) (sqrt((double) n) + 0.1);  
   // p,q,r,s will be <= B if they exist
   for(p=0;p<=B;p++)
   for(q=0;q<=B;q++)
   for(r=0;r<=B;r++)
   for(s=0;s<=B;s++)
   {  if(p*p+ q*q + r*r + s*s == n)
        { *a = p; *b = q; *c = r; *d = s; 
          return 0;
        }
   }
   assert(0);  // math says we'll always find p,q,r,s 
   return -1;
}  
 
int  fourSquares(long long n,int *a, int *b, int *c, int *d)
// find (if possible) four integers p,q,r,s such that 
// p <= q <= r <= s and 
// p^2 + q^2 + r^2 + s^2 == n, and write them into *a, *b, *c, *d
// respectively.  
// Return 0 for success or -1 if no such p,q,r,s exist.
// assumes n fits in 62 bits so its sqrt fits in an int.
  
{  long long p,q,r,s;
   long long psq, qsq, rsq, ssq;
   int B = (int) (sqrt((double) n) + 0.1);  
   // p,q,r,s will be <= B if they exist
   for(p=0;p<=B;p++)
   { psq = p*p;
     for(q=p, qsq = q*q;psq + qsq <= n;q++, qsq = q*q)
	 { long long psqplusqsq = psq + qsq; 
       for(r=q,rsq = r*r; psqplusqsq + rsq <=n;r++, rsq = r*r)
	   { ssq = n - psq-qsq-rsq;
		 s = (int) (sqrt((double) ssq) +0.1);
		 if(s*s == ssq)  // if ssq is a perfect square
			   // s*s will be done with int arithmetic if s is an int.
			   // so if ssq is more than 32 bits, it will never == s*s
		   { *a = (int) p; *b = (int) q;
             if(r <= s)
		        {*c = (int) r; *d = (int) s;
		        }
		     else
		        { *c = (int) s; *d = (int)r;
		        }
             return 0;
		   }
	   }
	 }
   }
   assert(0);  // math says we'll always find p,q,r,s 
   return -1;
}