// Four square decomposition
// Eric Conrad
// Descrption
//	This program displays all decompositions of an integer into
//	four squares using brute force.  The inner loop could be
//	optimized by using a better square root algorithm.

#include <stdlib.h>
#include <iostream.h>

typedef unsigned long ULONG, ULONG4[4];
typedef char SIGN4[4];

void process( ULONG );
void quadruple(ULONG, ULONG, ULONG, ULONG);
void quadruple(ULONG4, SIGN4, int);

int main(int argc, char** argv)
	{
	if(argc != 2)
		{
		cout << "Usage: " << argv[0] << " integer\n";
		return 1;
		}
	ULONG n = atol( argv[1] );
	process(n);
	return 0;
	}

void process( ULONG n )
	{
	if(n==0)
		{
		quadruple(0,0,0,0);
		return;
		}
	long a;
	for(a=0; a*a<=n; a++)
		{
		long b;
		long nb = n - a*a;
		if(nb % 8 == 7)
			continue;	// nb is not three-square summable

		for(b=0; b*b<=nb; b++)
			{
			long c;
			long nc = nb - b*b;
			if( nc%4 == 3 )
				continue; // nc is not two-square summable

			for(c=0; c*c<=nc; c++)
				{
				long d;
				long nd = nc - c*c;
				for(d=0; d*d<=nd; d++)
					{
					if(d*d==n-a*a-b*b-c*c)
						quadruple(a,b,c,d);
					}
				}
			}	
		}
	}

void quadruple(ULONG a, ULONG b, ULONG c, ULONG d)
	{
	ULONG4	arr;
	SIGN4	sig;
	arr[0] = a;
	arr[1] = b;
	arr[2] = c;
	arr[3] = d;
	quadruple(arr, sig, 0);
	}

void entry(char sig, ULONG val)
	{
	if(sig != ' ') cout << sig;
	cout << val;
	}

void entries(ULONG4 arr, SIGN4 sig)
	{
	cout << "(";
	for(int i=0; i<3; i++)
		{
		entry(sig[i], arr[i]);
		cout << ",";
		}
	entry(sig[3], arr[3]);
	cout << ")";
	cout << "\n";
	}

void quadruple(ULONG4 arr, SIGN4 sig, int level)
	{
	if(level>3)
		{
		entries(arr,sig);
		}
	else
		{
		sig[level] = ' ';
		quadruple(arr, sig, level+1);
		if(arr[level] != 0)
			{
			sig[level] = '-';
			quadruple(arr, sig, level+1);
			}
		}
	}