#include <stdio.h>
#include <malloc.h>
#include <string.h>

#define MAX(x,y) (x>y?x:y)

static char vcid[] = "$Id: factorial.cpp,v 1.2 2001/10/08 09:17:19 reeses Exp $";

char * add ( char *one, char *two )
{
//	printf("adding %s and %s\n", one == NULL? "null" : one, two == NULL? "null" : two);
	if ( one == NULL )
	{
		if ( two == NULL )
			return strdup("0");
		else
			return two;
	}
	else
		if ( two == NULL )
			return one;
	
	int len1 = strlen(one), 
		len2 = strlen(two),
		digit1=0, 
		digit2=0, 
		carry=0, 
		sum=0,
		maxLen = MAX(len1, len2),
		lenResult = maxLen;
	
	char *result = (char*)malloc( lenResult * sizeof(char));
	
	for ( int i = 0; i < maxLen || (carry != 0); ++i )
	{
		if ( i > lenResult )
		{
			lenResult += 40;
			result = (char*) realloc(result, lenResult*sizeof(char));
		}
		if ( i < len1 )
			digit1 = one[len1 - i - 1]-'0';
		if ( i < len2 )
			digit2 = two[len2 - i - 1]-'0';
		
		sum = digit1 + digit2 + carry;
		
		carry = sum/10;
		sum %= 10;
		
		result[i] = sum+'0';
		result[i+1] = 0;
		
		digit1=0;
		digit2=0;
	}
	return strrev(result);
}

char * decrement ( char *in )
{
	char *tmp = strrev(strdup(in)),
		*tmp2 = tmp;
	
	for (;;)
	{
		if ( *tmp2 > '0' )
		{
			(*tmp2)--;
			break;
		}
		else
		{
			*tmp2 = '9';
			tmp2++;
		}
	}
	
	strrev(tmp);
	while ( *tmp == '0' )
		tmp++;
	
	if ( strlen(tmp) == 0 )
		return "0";
	return tmp;
}

char * imul ( char *one, int two )
{
	char *result = NULL;
	if ( two == 0 )
		return strdup("0");
	if ( two == 1 )
		return strdup(one);
	while ( two-- > 0 )
		result = add(result, one);
	
	return result;
}

char * mul ( char * one, char * two )
{
	char *tmp1, 
		 *tmp2,
		 *result = NULL;
	
	int len1 = strlen(one),
		len2 = strlen(two);
	
	if ( len1 >= len2 )
	{
		tmp1 = one;
		tmp2 = two;
	}
	else
	{
		tmp1 = two;
		tmp2 = one;
		len1 = strlen(tmp1);
		len2 = strlen(tmp2);
	}
	
	for ( int i = 0; i < len2; ++i )
	{
		char *product = imul(tmp1, tmp2[(len2-i)-1]-'0');
		
		if ( i > 0 )
		{
			int lenp = strlen(product);
			product = (char*) realloc(product, (lenp+i) * sizeof(char));
			for ( int j = lenp-1; j < (lenp+i); j++ )
				product[j] = '0';
			product[lenp+i] = 0;
		}
		
		result = add(result, product);
	}
	return result;
}

char * fact ( char *in )
{
	if ( strcmp (in, "0") == 0 )
		return "1";
	return mul(in, fact(decrement(in)));
}

int main(int argc, char ** argv)
{
	printf("%s! = %s\n", argv[1], fact(strdup(argv[1])));
	
	return 0;
}