main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX(a, b) a > b ? a : b;

typedef struct 
{
  int *digits;
	size_t digitCount;
} LongNumber, *pLongNumber;

void FreeNumber(pLongNumber);
void ShiftNumber(pLongNumber, unsigned);
pLongNumber MulByInt(pLongNumber, int);

pLongNumber CreateNumber(const char* st)
{
	int i;
	pLongNumber number = (pLongNumber)malloc(sizeof(LongNumber));
	number->digitCount = strlen(st);
	number->digits = (int*)malloc(sizeof(int) * number->digitCount);
	for(i = 0; i < number->digitCount; ++i)
	{
		number->digits[i] = st[number->digitCount - i - 1] - '0';
	}
	return number;
}

pLongNumber Add(pLongNumber a, pLongNumber b)
{
	int i;
	int c = 0;
	pLongNumber number = (pLongNumber)malloc(sizeof(LongNumber));
	number->digitCount = MAX(a->digitCount, b->digitCount);
	number->digits = (int*)calloc(number->digitCount + 1, sizeof(int));
    for (i = 0; i < b->digitCount; ++i) {
        if (i >= a->digitCount) {
			number->digits[i] = 0;
        }
        c += a->digits[i] + b->digits[i];
        number->digits[i] = c % 10;
        c /= 10;
    }
    for (i = b->digitCount; c > 0 && i < number->digitCount; ++i) {
        c += a->digits[i];
        number->digits[i] = c % 10;
        c /= 10;
    }
    number->digits[number->digitCount] = c;
    number->digitCount += (c == 0) ? 0 : 1;
}

pLongNumber Mul(pLongNumber a, pLongNumber b)
{
	int i;
	pLongNumber number = (pLongNumber)malloc(sizeof(LongNumber));
	number->digitCount = a->digitCount + b->digitCount;
	number->digits = (int*)calloc(number->digitCount, sizeof(int));
	for(i = 0; i < b->digitCount; ++i)
	{
		pLongNumber sum;
		pLongNumber temp = MulByInt(a, b->digits[i]);
		ShiftNumber(temp, i);
		sum = Add(number, temp);
		FreeNumber(number);
		FreeNumber(temp);
		number = sum;
	}
	while(number->digits[number->digitCount-1] == 0 && number->digitCount > 1)
		number->digitCount -= 1;
 	return number;
}

pLongNumber MulByInt(pLongNumber a, int b)
{
	int i;
	long long c = 0;
	pLongNumber number = (pLongNumber)malloc(sizeof(LongNumber));
	number->digitCount = a->digitCount;
	number->digits = (int*)calloc(number->digitCount + 9, sizeof(int));
	for(i = 0; i < a->digitCount; ++i)
	{
		c += a->digits[i] * b;
		number->digits[i] = c % 10;
		c /= 10;
	}
	while(c != 0)
	{
		number->digits[number->digitCount++] = c % 10;
		c /= 10;
	}
	return number;
}

void PrintNumber(pLongNumber number)
{
	int i;	
	for(i = number->digitCount-1; i >= 0; --i)
	{
		printf("%d", number->digits[i]);
	}
	printf("%s", "\n");
}

void FreeNumber(pLongNumber number)
{
	free(number->digits);
	free(number);
}

void ShiftNumber(pLongNumber number, unsigned shift)
{
	int i;
	int *ptr = number->digits;
	ptr = number->digits = (int*)realloc(ptr, (number->digitCount + shift) * sizeof(int));
	memmove(ptr + shift, ptr, sizeof(int) * number->digitCount);
	memset(number->digits, 0, sizeof(int) * shift);
	number->digitCount += shift;
}

pLongNumber InputNumber()
{
	char buf[300];
	scanf("%s", buf);
	return CreateNumber(buf);
}

pLongNumber Factorial(int n)
{
	pLongNumber number, temp;
	int i;
	number = CreateNumber("1");
	for(i = 1; i <= n; ++i)
	{
		temp = MulByInt(number, i);
		FreeNumber(number);
		number = temp;
	}
	return number;
}

pLongNumber Fib(int n)
{
	pLongNumber fib1, fib2, fibSum;
	int i = 2;
	fib1 = CreateNumber("1");
	fib2 = CreateNumber("1");
	while(i < n)
	{
		fibSum = Add(fib1, fib2);
		FreeNumber(fib1);
		fib1 = fib2;
		fib2 = fibSum;
		++i;
	}
	FreeNumber(fib1);
	return fibSum;
}

int main()
{
	pLongNumber number1, number2, number;
	char buf1[100], buf2[100];
	int num;
	/*scanf("%s", buf1);
	scanf("%s", buf2);
	number1 = CreateNumber(buf1);
	number2 = CreateNumber(buf2);
	number = Mul(number1, number2);
	printf("%s", "Here is product: ");
	PrintNumber(number);
	FreeNumber(number);*/
	clock_t before = clock();
	number = Factorial(250);
	printf("\nTime: %.4f\n", (float)(clock() - before) / CLOCKS_PER_SEC);
	//printf("%s", "\nHere is 1000!: ");
	PrintNumber(number);
	FreeNumber(number);
	return 0;
	number = Fib(1000);
	printf("%s", "\nHere is 1000th Fibonacci number: ");
	PrintNumber(number);
	FreeNumber(number);
	FreeNumber(number1);
	FreeNumber(number2);
	return 0;
}