大整数阶乘的计算 N!

1、先说小点的数的阶乘计算：

// n!	
unsigned long fac(int n)
{
	if(n == 0)
		return 1;
	else
		return n * fac(n - 1);
}

2、如果需要稍微提高效率，还可以：

unsigned long fac_ex(int n)
{
	if(n == 0 || n == 1)
		return 1;
	else
		return n * (n - 1) * fac(n - 2);
}

3、依此类推，继续想提高一点效率：

unsigned long fac_ex1(int n)
{
	if(n == 0 || n == 1)
		return 1;
	else if(n == 2)
		return 2;
	else
		return n * (n - 1) * (n - 2) * fac(n - 3);
}

unsigned long fac_ex3(int n)
{
	if(n == 0 || n == 1)
		return 1;
	else if(n == 2)
		return 2;
	else if(n == 3)
		return 6;
	else
		return n * (n - 1) * (n - 2) * (n - 3) * fac(n - 4);
}

4、如果不像用递归，那就用下面的，效率比递归的要好：

unsigned long fac_ex2(int n)
{
	unsigned long ret = 1;
	for(int i = 2; i <= n; ++i)
	{
		ret *= i;
	}
	return ret;
}

5、如果对空间要求不高，可以把一些数据计算出来，放在静态区：

unsigned long fac_ex10(int n)
{
	static int facArr[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,
	fac_ex2(11)};		// fac_ex2(11) will be calculated only once
	if(n >= 0 && n < sizeof(facArr) / sizeof(facArr[0]))
		return facArr[n];
	else
		return n * (n - 1) * (n - 2) * (n - 3) * (n - 3) * (n - 3)
		 * (n - 4) * (n - 5) * (n - 6) * (n - 7) * (n - 8) * (n - 9)
		 * (n - 10) * fac(n - 11);
}

6、上面的是放在函数里面，也可以放在文件作用域里或全局作用域：

static int facArr[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,
	fac_ex2(11)};	// fac_ex2(11) will be calculated only once, at the initialization of the app

7、上面的不讨论了，现在讨论大整数阶乘：

// 大整数阶乘		
void	fac_bigInteger(int n, int result[], int maxSize, int *resultLen)
{
	if(maxSize < 1)
		return;
	memset(result, 0, maxSize * sizeof(int));
	result[0] = 1;
	int currLen = 1;
	
	for(int j = 2; j <= n; ++j)
	{
		int carry = 0;
		for(int k = 0; k < maxSize && k < currLen; ++k)
		{
			int temp = result[k] * j + carry;
			if(temp < 10)
			{
				result[k] = temp;
				carry = 0;
			}
			else
			{
				carry = temp / 10;
				result[k] = temp - carry * 10;
			}
		}
		if(carry > 0)
		{
			char buf[512];
			sprintf(buf, "%d", carry);
			int currLenTemp = currLen;
			for(int i = strlen(buf) - 1; i >= 0; --i)
			{
				result[currLenTemp++] = buf[i] - '0';
			}
			currLen = currLenTemp;
		}
	}
	*resultLen = currLen;
}

测试代码：

void ccTestFac()
{
#if 1	
	int arr[1024];
	int len;
	fac_bigInteger(50, arr, 1024, &len);
	for(int i = len - 1; i >= 0; --i)
	{
		std::cout << arr[i];
	}
	std::cout << endl;
	std::cout << len << std::endl;
	
#endif
}