之前一次面试出了这样一道题, 求一个大数, 例如 65535, 的阶乘.
求阶乘很简单, 但是如果数字很大的话就比较难办了. 这里受到力扣大数类题目总是对 1e9+7 取余的启发, 用一个数组存储一个大数, 数组的每一项都是 int64, 并且小于 1e9.
举个例子, 如果要用数组 num 存 111111111222222222 这样一个数, 那么 num[0] = 222222222, num[1] = 111111111.
两个小于 1e9 的 int64 数字相乘, 得到的结果仍在 int64 的范围内. 所以可以让乘数 x 与数组中的每一项做乘法, 得到积之后在对 1e9 取余数保留在数组这一项中, 高位进位到数组的下一项. 这个乘法的函数如下.
class LargeFactorial {
public:
LargeFactorial(long large_num = 1);
void print();
private:
// x 与 _num 表示的大数相乘
void mul(int64_t x) {
if (x <= 1) return;
// prefix 记录进位
int64_t prefix = 0;
for (int64_t& digit : _num) {
// x 与数组的每一项做乘法, 加上进位
digit = digit * x + prefix;
// 高位进位
prefix = digit / _MOD;
// 低位保留
digit = digit % _MOD;
}
while (prefix) {
_num.push_back(prefix % _MOD);
prefix /= _MOD;
}
}
long _MOD = 1e9;
// _num 表示现在已有的大数
vector<int64_t> _num;
};
实例化一个类 LargeFactorial 要传入需要求阶乘的大数, 构造函数内求该数的阶乘. 构造函数如下.
class LargeFactorial {
public:
LargeFactorial(long large_num = 1) : _num({1}) {
while (large_num > 1) {
mul(large_num);
--large_num;
}
}
void print();
private:
void mul(int64_t x);
long _MOD = 1e9;
vector<int64_t> _num;
};
函数 print 输出大数, 因为 _num 是低位优先存储, 输出时要从后往前输出. 此外还要注意处理某一项以 0 开头的情况. 这里在处理每一项时用一个 string 一位一位处理大数.
class LargeFactorial {
public:
LargeFactorial(long large_num);
void print() {
string s;
// 输出数组最后一项, 不需要特殊处理
cout << _num.back();
for (int i = _num.size() - 2; i >= 0; --i) {
// 因为每一项都小于 1e9,
// 这里用 9 个 0 处理每一项
s = "000000000";
int x = _num[i];
int idx = 8;
while (x) {
s[idx--] = (x % 10 + '0');
x /= 10;
}
cout << s;
}
cout << endl;
}
private:
void mul(int64_t x);
long _MOD = 1e9;
vector<int64_t> _num;
};
在主函数中可以调用这个类求大数的阶乘.
int main() {
long large_num = 65536;
if (argc > 1) large_num = atoi(argv[1]);
LargeFactorial large_factorial(large_num);
large_factorial.print();
return 0;
}
经过验证, 该程序正确输出 $100!$.
本文阐述了如何计算一个大数的阶乘, 其中最关键的部分就是存储一个大数 num 以及把这个大数与一个数字 x 相乘. 现阶段要求 x < 1e9, 即 x 是一个小数. 后续可以探索当 x 也是用数组存储的大数时如何做乘法. 另一个扩展的点就是用多线程进行加速计算. 本文代码见 Sunjnn/largeFactorial: Calculate the factorial of a large number (github.com).