1. 为什么高位数阶乘值得单独拿出来聊阶乘这个运算几乎每个写过代码的人都在入门阶段碰过。5! 12010! 3628800用计算器按两下就出来了。但真正把数字往上推比如算100!、1000!甚至10000!情况就完全不一样了。我第一次被阶乘教育是在帮一个做组合数学的朋友验证一组排列数的时候随手写了个递归函数输入30结果屏幕上蹦出来一个负数。当时我还以为是编译器出了问题后来才反应过来——int溢出了。这就是高位数阶乘的核心矛盾数学上阶乘增长极快而计算机原生整数类型能表示的范围极其有限。64 位无符号整数最大也就18446744073709551615而21!已经超过这个量级了。换句话说只要你想算21以上的阶乘就不能再依赖语言自带的整数类型必须自己处理大数。所以这篇内容想聊的不是阶乘怎么写而是当结果远超原生类型上限时怎么用 MATLAB、Python、C 这三种风格迥异的工具把它算出来并且算得对、算得快、算得省心。三种语言在这里代表了三种完全不同的思路Python 有内置大整数属于开箱即用MATLAB 有符号工具箱和向量化属于科研顺手C 语言什么都没有必须手搓大数乘法属于底层硬核。把这三条路线放在一起对比能非常清楚地看到语言抽象层次对同一个问题的不同解法。适合谁看如果你正在学编程、准备算法面试、做组合数学或概率统计的作业、又或者单纯好奇1000 的阶乘到底长什么样这篇都能给你可直接抄作业的代码和踩坑经验。下面我会先讲清楚大数阶乘的通用原理再分别给出三种语言的完整实现最后把性能、精度、易用性拉一张表对比并附上我实际调试时遇到的各种坑。2. 高位数阶乘的底层原理与方案选型2.1 阶乘为什么会溢出从 21 这个临界点说起先把溢出的边界算清楚这样你才知道什么时候必须上大数方案。以常见的 64 位有符号整数long long上限约9.22 × 10^18为例nn! 的近似值是否超出 64 位有符号整数202.43 × 10^18否刚好放得下215.11 × 10^19是溢出251.55 × 10^25是503.04 × 10^64是1009.33 × 10^157是可以看到20!是 64 位有符号整数能表示的最后一个阶乘21!就翻车了。而100!有 158 位十进制数字1000!有 2568 位10000!有 35660 位。这个位数增长大致遵循斯特林公式的估算log10(n!) ≈ n·log10(n) - n·log10(e) 0.5·log10(2πn)拿n 1000代入1000 × 3 - 1000 × 0.4343 0.5 × log10(6283) ≈ 3000 - 434.3 1.9 ≈ 2567.6和实际 2568 位几乎一致。这个公式的实用价值在于你可以在动手算之前先估算结果需要多少位存储空间从而决定数组开多大、内存够不够。2.2 大数阶乘的通用算法数组模拟手工乘法不管哪种语言只要没有内置大整数核心思路都是一样的——用一个数组的每一位存一个十进制数字然后模拟小学竖式乘法。具体来说用一个整型数组digits[]digits[0]存个位digits[1]存十位以此类推低位在前方便进位。从2开始逐个乘到n。每乘一个数k就遍历当前所有有效位做digits[i] * k carry取模 10 存回本位整除 10 作为进位。乘完一轮后把剩余的进位一位一位地追加到数组末尾。最后倒序输出数组就是结果。这个算法的时间复杂度是O(n × 位数)对于n 1000来说位数约 2568总操作量在百万级别任何语言都能秒出。真正的性能瓶颈出现在n上万甚至更大时这时候就要考虑更高效的算法比如分治乘法或者基于快速傅里叶变换的大数乘法不过那是另一个话题了日常使用数组模拟完全够。2.3 三种语言的路线差异为什么不能一套代码走天下选型这件事本质上是看你的使用场景和对性能/精度的要求Python内置int就是任意精度大整数math.factorial(1000)一行搞定底层是 C 实现速度快且绝对精确。适合快速验证、脚本处理、教学演示。缺点是如果你要理解算法本身用它就看不到过程。MATLAB默认的double只有约 15 位有效数字直接算阶乘从21!开始就不精确了。但 MATLAB 提供了符号工具箱symfactorial(sym(1000))能得到精确结果。适合科研场景下和矩阵运算、公式推导混用。缺点是符号运算慢且依赖工具箱。C 语言没有任何内置大数支持必须手写数组乘法。适合学习算法本质、嵌入式环境、或者对性能有极致要求的场景。缺点是代码量大容易在进位、数组越界上出错。我个人的经验是先用 Python 快速拿到正确答案作为基准再用 C 实现去对比验证MATLAB 则用于需要和符号推导结合的场合。这个三语言互验的习惯帮我抓出过好几次 C 代码里的进位 bug。3. Python 实现站在内置大整数的肩膀上3.1 一行代码方案与它的边界Python 最省事的写法就是直接调用标准库import math def factorial_builtin(n): return math.factorial(n) print(factorial_builtin(100))math.factorial底层是 C 实现的对n有整数类型要求传入浮点数会报TypeError。它内部还做了一些优化比如对较小的n用查表对大n用分治策略所以速度比你自己写的循环还快。实测math.factorial(10000)在我的机器上大约 20 毫秒左右100000也就一两秒。但这里有个容易被忽略的点Python 3.11 之后对超大整数转字符串做了限制。如果你算完100000!想直接print或者str()可能会触发ValueError: Exceeds the limit (4300 digits) for integer string conversion。这是为了防止恶意构造的超长数字拖垮程序。解决办法是临时调高限制import sys sys.set_int_max_str_digits(1000000) # 按需调大这个坑我在处理50000!的时候踩过当时还以为是内存不够排查了半天才发现是这个安全限制。3.2 手写循环版理解大数乘法的过程如果你想看清楚大数是怎么一位一位长出来的可以自己写循环版def factorial_loop(n): result 1 for i in range(2, n 1): result * i return result这段代码看起来平平无奇但result * i背后Python 解释器每次都在做一次大整数乘法。当result有几千位时每次乘法的开销就上来了。实测factorial_loop(10000)比math.factorial(10000)慢好几倍因为标准库用了更聪明的分治算法而循环版是老老实实一位一位乘。不过循环版的价值在于可读性和可调试性。你可以在循环里加打印观察result的位数增长这对理解阶乘的量级非常有帮助。我经常用它来给学生演示为什么 100 的阶乘长得像一串随机数字。3.3 用 Python 做基准验证的实操心得Python 最大的价值在我看来是当基准真值。当你写 C 或 MATLAB 版本时怎么知道结果对不对最靠谱的办法就是拿 Python 的结果去比对。我通常这样做import math def verify(candidate_result, n): truth str(math.factorial(n)) candidate str(candidate_result) if truth candidate: print(f{n}! 验证通过共 {len(truth)} 位) else: # 找出第一个不一致的位置 for idx, (a, b) in enumerate(zip(truth, candidate)): if a ! b: print(f第 {idx} 位不一致真值 {a}你的结果 {b}) break这个verify函数帮我定位过无数次 bug。有一次 C 版本在n 50时结果只差最后几位用这个函数一比对发现是进位处理时漏掉了最高位的进位。如果没有逐位比对光看两个几千位的数字肉眼根本找不出差异。提示做基准验证时建议从n 20开始逐级往上测20、21、25、50、100……因为小数值能快速暴露逻辑错误大数值则考验进位和数组扩容的正确性。4. MATLAB 实现符号运算与向量化的取舍4.1 为什么 double 从 21 开始就不准了MATLAB 默认数值类型是双精度浮点double它遵循 IEEE 754 标准尾数只有 52 位能精确表示的整数上限是2^53 9007199254740992约 9 × 10^15。而18! 6402373705728000还在这个范围内19! 121645100408832000就已经超过2^53了21!更是远远超出。所以factorial(20) % 精确 factorial(21) % 开始出现误差 factorial(100) % 结果是一串科学计数法完全不是精确值如果你用factorial(100)得到9.3326e157这只是个近似值后面几十位全是浮点误差。做科研时如果拿这个去参与后续精确计算误差会累积放大。4.2 sym 符号工具箱拿到精确结果的正确姿势要精确计算必须用符号工具箱n 1000; result factorial(sym(n)); disp(result)sym(n)把n转成符号对象factorial对符号对象会走精确的大整数运算路径。得到的结果是符号类型可以用char(result)转成字符串或者用num2str处理。实测factorial(sym(1000))大约需要几百毫秒比 Python 慢但胜在和 MATLAB 的符号推导体系无缝衔接。这里有个细节符号结果转字符串时默认不会用科学计数法而是完整展开。这对需要精确数字的场景很友好但如果你只是想看个大概double(result)会把它转回浮点注意这时候精度就丢了。4.3 向量化思路能不能不用循环MATLAB 的强项是向量化但阶乘有个天然的串行依赖——每一步都依赖上一步的结果所以纯向量化做不了精确大数阶乘。不过对于求阶乘的对数这种场景向量化就非常香n 1:1000; log_factorial cumsum(log(n)); % log(n!) sum(log(1..n))这个技巧在概率统计里算对数似然时特别常用因为直接算n!会溢出取对数后累加就稳定多了。我做过一个二项分布相关的项目就是用cumsum(log(1:n))来避免大数阶乘的溢出问题比直接调factorial再取对数精确得多。注意cumsum(log(n))得到的是log(n!)的近似值因为浮点对数本身有误差。如果对精度要求极高还是得用sym算精确阶乘再取对数。4.4 MATLAB 实操中的两个坑第一个坑是符号工具箱的版本差异。老版本 MATLAB 里factorial(sym(n))可能报错需要改用prod(sym(1:n))。后者是显式连乘速度慢一些但兼容性更好。我建议你两个都试一下看哪个在你的版本上能跑通。第二个坑是大 n 时的内存占用。sym类型存储大整数时内部用的是字符串或特殊结构10000!有 35660 位符号对象会占用可观内存。如果你要批量算很多个阶乘记得及时clear掉不用的符号变量否则内存会悄悄涨上去。5. C 语言实现手搓大数乘法的完整过程5.1 数组设计低位在前还是高位在前C 语言实现大数阶乘第一步是决定数组怎么存。我强烈建议低位在前也就是digits[0]存个位。原因很简单乘法是从低位往高位算的进位也是往高位传低位在前时数组下标增长方向和进位方向一致代码写起来最自然。如果高位在前每次进位都要往前插还得整体搬移数组纯属自找麻烦。数组大小怎么定用前面讲的斯特林公式估算位数再留点余量。比如算n 1000估算约 2568 位那就开3000的数组。稳妥起见我一般按n × log10(n)再乘个 1.2 的系数来开#include stdio.h #include stdlib.h #include math.h int main() { int n 1000; // 估算所需位数留 20% 余量 int max_digits (int)(n * log10(n 1 ? n : 2)) 10; int *digits (int *)calloc(max_digits, sizeof(int)); digits[0] 1; int len 1; // 当前有效位数 // ... 后续乘法 }用calloc而不是malloc是因为它会把数组清零省得你手动初始化。这个细节看似小但如果你忘了清零高位残留的垃圾值会直接污染结果。5.2 核心乘法循环与进位处理核心逻辑就是两层循环外层遍历2到n内层遍历当前所有有效位做乘法for (int k 2; k n; k) { int carry 0; for (int i 0; i len; i) { int product digits[i] * k carry; digits[i] product % 10; carry product / 10; } // 处理剩余进位 while (carry 0) { digits[len] carry % 10; carry / 10; len; } }这段代码的关键在while (carry 0)这个循环。很多人第一次写的时候只写if (carry 0)结果当进位超过一位时就丢了。比如digits[i] * k最大可能是9 × 1000 9000加上进位可能上万carry会有好几位必须用while一位一位地拆出来。还有一个隐患是数组越界。如果max_digits估算偏小digits[len]就会写到数组外面去程序可能崩溃也可能悄悄改坏别的内存。我的习惯是在while循环里加个边界检查while (carry 0) { if (len max_digits) { fprintf(stderr, 数组越界请增大 max_digits\n); exit(1); } digits[len] carry % 10; carry / 10; }这个检查在调试阶段能救命正式跑的时候可以去掉以省点开销。5.3 输出与验证倒序打印与逐位比对算完之后数组里是低位在前的结果输出时要倒着打for (int i len - 1; i 0; i--) { printf(%d, digits[i]); } printf(\n);验证环节我一般把 C 的输出重定向到文件再用 Python 脚本逐位比对。前面提到的verify函数在这里就派上用场了。实测1000!的 C 版本在我的机器上大约 5 毫秒比 Python 的math.factorial还快一点因为 C 没有解释器开销而且我的数组是连续内存缓存友好。5.4 性能优化从 O(n²) 到分治的思考朴素的数组乘法是O(n × 位数)当n到十万级别时就开始吃力了。这时候可以考虑几个优化方向压位存储不要一位存一个数字而是一位存 4 位或 9 位用一个int存0~9999或0~999999999。这样数组长度缩短到原来的 1/4 或 1/9乘法次数大幅减少。代价是进位逻辑要改成按10000或10^9取模。分治乘法把1到n分成两半分别算阶乘再相乘递归下去。这样能把大数乘法的次数从n次降到log n次配合快速乘法如 Karatsuba效果显著。多线程把乘法任务拆到多个线程但要注意大数乘法的依赖关系实现起来复杂收益不一定高。日常使用压位存储是性价比最高的优化。我做过测试压 4 位后10000!的计算时间能降到原来的三分之一左右。不过压位会让代码可读性下降建议先用一位一存把逻辑跑通再考虑优化。6. 三语言对比与常见问题排查6.1 性能、精度、易用性横向对比把三种实现放在一起差异一目了然维度PythonMATLABC精度内置任意精度绝对精确需sym工具箱否则 21! 起失真手写数组精确但依赖实现正确性易用性一行math.factorialfactorial(sym(n))一行需几十行代码速度1000!约 20 ms约 300 ms约 5 ms速度10000!约 200 ms数秒约 100 ms代码量极少极少中等适用场景脚本、验证、教学科研、符号推导算法学习、嵌入式、极致性能主要坑点字符串转换位数限制默认 double 精度不足进位、数组越界从表里能看出一个规律抽象层次越高代码越短但你对底层的控制力越弱。Python 和 MATLAB 把大数运算封装好了你享受便利的同时也失去了优化空间C 什么都要自己来但每一步都在你掌控之中。6.2 常见问题速查表下面这张表是我在实际调试中整理出来的覆盖了三种语言最常遇到的问题现象可能原因排查与解决结果从某位开始全错进位处理漏了多位进位检查while (carry)是否写成if结果末尾多出乱码数字数组未初始化用calloc或手动清零程序崩溃或结果诡异数组越界增大max_digits加边界检查Python 报字符串转换错误超过 4300 位限制sys.set_int_max_str_digits调大MATLAB 结果不精确用了 double 而非 sym改用factorial(sym(n))大 n 时内存暴涨符号对象或数组未释放及时clear或free结果位数不对位数估算公式用错用斯特林公式重新估算6.3 我踩过的三个真实坑第一个坑是C 语言里int溢出。早期我用int product digits[i] * k carry当k较大时digits[i] * k可能超过int上限约 21 亿。比如9 × 100000 900000加上进位也还好但如果压位存储用10^9进制digits[i] * k轻松破十亿再乘个k就溢出了。解决办法是用long long存中间结果。第二个坑是MATLAB 符号结果转数值时精度丢失。我有次算完factorial(sym(100))想把它转成double参与后续矩阵运算结果精度直接掉到 15 位。后来改成全程用sym运算最后才转字符串输出才保证了精度。第三个坑是Python 的递归深度。有人喜欢用递归写阶乘factorial(n) n * factorial(n-1)。但 Python 默认递归深度只有 1000 左右算1000!直接RecursionError。而且递归版对每个n都新建栈帧内存开销大。阶乘这种线性依赖的问题永远优先用循环不要用递归。提示如果你确实想用递归记得sys.setrecursionlimit调高上限但更推荐直接改成循环既快又安全。7. 实际应用场景与扩展方向7.1 组合数学与概率统计中的阶乘高位数阶乘最直接的应用就是组合数C(n, k) n! / (k! × (n-k)!)。当n很大时直接算三个阶乘再相除中间结果会巨大无比。更聪明的做法是边乘边除或者取对数后用lgamma函数import math def log_comb(n, k): return math.lgamma(n 1) - math.lgamma(k 1) - math.lgamma(n - k 1)lgamma算的是log(Γ(x))而Γ(n1) n!所以这个公式能直接给出log(C(n,k))完全避开大数溢出。我在做二项分布概率计算时全程用对数域运算最后再exp回来稳定性比直接算阶乘好太多。7.2 大数阶乘的位数估算与斯特林公式有时候你不需要阶乘的具体值只想知道它有多少位。这时候斯特林公式就派上用场了import math def factorial_digits(n): if n 2: return 1 # log10(n!) 的斯特林近似 log10_fact n * math.log10(n) - n * math.log10(math.e) 0.5 * math.log10(2 * math.pi * n) return int(log10_fact) 1实测factorial_digits(1000)返回 2568和实际位数完全一致。这个技巧在需要预分配内存或者判断结果规模时非常实用避免了先算出来再数字符串的浪费。7.3 从阶乘延伸出去的大数运算阶乘只是大数运算的一个入口。掌握了数组模拟乘法你就能顺势实现大数的加法、减法、甚至幂运算。比如算2^1000思路和阶乘几乎一样只是把乘k换成乘2重复 1000 次。再进一步大数除法、取模、进制转换都是同一套数组思路的变体。我个人的学习路径是先用阶乘把数组存大数 模拟竖式运算这套思维建立起来再去啃更复杂的大数库源码。等你手写过一遍大数乘法再回头看 Python 的int实现或者 GMP 库会有种原来如此的通透感。最后分享一个我常用的调试技巧永远先用小数值验证逻辑再放大到目标规模。算1000!之前先确保20!、21!、50!都对因为小数值下你能肉眼核对结果大数值下只能靠程序比对。这个习惯帮我省下了大量排查时间也推荐给你。