Tính giai thừa của số lớn

Một hôm có bạn hỏi tôi cách tính giai thừa của số lớn. Tất nhiên nếu bạn tính theo cách bình thường thì sẽ lỗi vì một số kiểu dữ liệu số nguyên trong một số ngôn ngữ độ dài không đủ để chứa. Vì thế ta cần viết thuật toán để nhân số với một số lưu ở trong mảng (mỗi phần tử của mảng là một con số của số mà ta nhân)

Ví dụ nhé:Bình thường ta nhân 12*13 thì cần làm gì ?
12*3 = 36 viết 6 nhớ 3
12*1 = 12 + 3 (nhớ phía trên) = 15 viết 5 nhớ 1
Viết 1 : (còn lại)
Như vậy kết quả là 156 viết theo thứ tự từ dưới lên

Áp dụng:
Ta lưu 13 vào mảng với dạng {3,1}
Sau đó ta nhân 12 với {3,1} thì sẽ được mảng {6,5,1} lúc này viết thêm đoạn đảo ngược mảng ta sẽ được {1,5,6}

Như vậy ta sẽ viết được hàm tính 100! dưới đây

	#include<iostream>
	using namespace std;
	#define MAX 500
	int multiply(int x, int res[], int res_size);
	void factorial(int n)
	{
	int res[MAX];
	res[0] = 1;
	int res_size = 1;
	for (int x=2; x<=n; x++)
	{
	res_size = multiply(x, res, res_size);
	}
	cout << "Factorial of given number is \n";
	for (int i=res_size-1; i>=0; i--)
	cout << res[i];
	}
	int multiply(int x, int res[], int res_size)
	{
	int carry = 0;
	for (int i=0; i<res_size; i++)
	{
	int prod = res[i] * x + carry;
	res[i] = prod % 10;
	carry = prod/10;
	}
	while (carry)
	{
	res[res_size] = carry%10;
	carry = carry/10;
	res_size++;
	}
	return res_size;
	}
	int main()
	{
	factorial(200);
	return 0;
	}

view raw factorialbig.cpp hosted with ❤ by GitHub