1. 从一道“老题”说起高位数阶乘到底难在哪阶乘这个运算几乎每个学过编程的人都在入门阶段写过。n! 1 × 2 × 3 × ... × n定义简单到一句话就能说清。但如果你真的动手算过100!、1000!甚至10000!就会发现事情远没有想象中那么轻松。我第一次被阶乘“教育”是在帮一个做组合数学的朋友验证一组排列数结果时随手用计算器敲50!得到的却是一个带科学计数法的近似值尾数全被抹掉了。那一刻我才意识到高位数的阶乘计算本质上不是一个“乘法”问题而是一个“大数表示与存储”的问题。所谓高位数阶乘通常指结果远超标准数据类型表示范围的阶乘运算。以 C 语言为例unsigned long long最大能表示约1.8 × 10^19而21!就已经是5.1 × 10^19直接溢出。20!是分水岭21!开始常规整型就彻底歇菜了。Python 稍微好一点内置任意精度整数1000!也就一行代码的事但如果你要算100000!那又是另一场关于时间和内存的博弈。MATLAB 默认的double类型只有约 15 到 16 位有效数字factorial(22)之后的结果就不再精确。所以这个项目的核心价值不在于“会写阶乘”而在于理解不同语言、不同工具在处理超大整数时的底层机制差异并据此选择或设计合适的算法。它适合三类人一是正在学 C 语言、想搞懂数组模拟大数运算的学生二是用 Python 做科学计算、想知道内置大整数到底靠不靠谱的开发者三是用 MATLAB 做数值分析、需要判断什么时候该切换到符号运算的研究者。下面我会把三种实现路径逐一拆开讲清楚每一步为什么这么做以及我踩过的那些坑。2. 三种实现路径的整体设计与选型逻辑2.1 为什么不能“一把梭”用内置类型很多人第一反应是Python 不是有无限精度整数吗直接math.factorial(n)不就行了这话对一半。Python 的int确实是任意精度底层用数组存储“数字位”理论上只要内存够算多大都行。但问题在于时间复杂度。朴素的高精度乘法是 O(n²) 级别的Python 内置的阶乘实现虽然做了优化比如分治乘法但当你算到10^6级别时耗时依然会以肉眼可见的速度增长。我实测过math.factorial(100000)大概几秒math.factorial(1000000)就要好几分钟而且内存占用相当可观。C 语言没有内置大整数必须自己用数组模拟。这看似麻烦但好处是完全可控你可以决定每一位存几位十进制数、用什么进制做内部运算、乘法怎么进位。这种“手搓”的过程恰恰是理解大数运算本质的最佳途径。MATLAB 则介于两者之间它有Symbolic Math Toolbox提供的sym类型可以做精确运算但符号运算速度慢且不是所有环境都装了工具箱。所以三条路径各有适用场景不能简单说谁替代谁。2.2 三种方案的核心思路对比我把三种实现的核心策略整理成一张表方便你快速判断该用哪种。维度C 语言数组模拟Python 内置 intMATLAB sym/数组数据表示整型数组每位存若干位十进制任意精度整数对象符号对象或双精度数组精度完全精确完全精确sym 精确double 不精确速度中等取决于进制选择快有底层优化sym 较慢代码量多需手写乘法和进位极少一行调用少但需工具箱学习价值高理解大数运算本质低黑盒中理解符号计算适用规模万位以内较舒适十万位以上仍可千位以内较稳从这张表能看出来如果你的目标是学习和理解C 语言数组模拟是首选如果目标是快速拿到结果Python 内置函数最省事如果是在 MATLAB 环境里做符号推导那就用sym。我个人的习惯是先用 Python 快速验证结果再用 C 语言复现一遍确认自己真的懂了原理MATLAB 则留给需要和符号表达式打交道的场合。2.3 一个容易被忽略的选型细节内部进制不管哪种语言只要涉及手写大数乘法就绕不开一个选择内部用十进制还是更高进制。很多人图省事数组每一位存一个 0 到 9 的数字乘法时逐位相乘再处理进位。这样写逻辑最直观但效率低因为每一位的“信息密度”只有 log₂10 ≈ 3.32 比特。如果改成每位存 0 到 9999即万进制信息密度提升到约 13.3 比特同样的数字位数减少到四分之一乘法和进位的循环次数大幅下降。我做过一个粗略的对比算5000!十进制逐位实现大约需要几秒而万进制实现通常能快三到五倍。这个差距在位数越多时越明显。所以后面讲 C 语言实现时我会直接采用万进制而不是教科书里常见的十进制逐位。这个选择背后的逻辑就是用空间换时间用更宽的“位”减少循环次数。3. C 语言数组模拟手搓大数乘法的完整实操3.1 数据结构设计与初始化C 语言实现高位数阶乘核心就是用一个整型数组来存结果的每一位。我采用万进制也就是数组每个元素存 0 到 9999 之间的一个数代表结果中的“一段”。比如结果123456789在万进制下存成[6789, 2345, 1]低位在前高位在后。为什么低位在前因为乘法是从低位开始产生进位低位在前处理起来最自然进位直接往后推即可。数组大小需要预先估算。n!的位数可以用斯特林公式近似log10(n!) ≈ n·log10(n) - n·log10(e) 0.5·log10(2πn)。以n 10000为例位数约 35660 位万进制下需要约 8915 个元素。为了保险我通常开n的大小再乘个系数或者直接用公式算完加 10 个余量。初始化时数组第一位设为 1其余为 0表示当前结果为 1。#include stdio.h #include string.h #define MAX_DIGITS 100000 // 万进制下的最大段数 int result[MAX_DIGITS]; int main() { int n 1000; memset(result, 0, sizeof(result)); result[0] 1; int len 1; // 当前有效段数 // 后续乘法... }这里len记录当前结果占用了多少段避免每次都遍历整个数组。这个细节很关键否则算10000!时每轮都扫十万个元素白白浪费大量时间。3.2 逐轮相乘与进位处理阶乘的本质是1 × 2 × 3 × ... × n所以外层循环从 2 到 n每次把当前结果乘以这个数。乘法的做法是用当前乘数i去乘结果数组的每一段加上来自低位的进位然后取模得到当前段的新值整除得到新的进位。for (int i 2; i n; i) { int carry 0; for (int j 0; j len; j) { int prod result[j] * i carry; result[j] prod % 10000; carry prod / 10000; } while (carry 0) { result[len] carry % 10000; carry / 10000; len; } }这段代码看起来简单但有几个坑必须注意。第一prod的类型必须是int或更大因为result[j]最大 9999i最大可能到几万乘积接近 10^8int通常够用但如果n更大就要考虑long long。第二进位carry在每轮乘法开始前要清零这个容易漏。第三内层循环只遍历到len而不是整个数组这是效率的关键。3.3 输出格式与边界处理算完之后数组里存的是万进制的段输出时要特别小心。最高位那段直接打印不需要补零后面的每一段都必须补足四位否则[6789, 2345, 1]会打成678923451丢掉了中间的零。printf(%d, result[len - 1]); for (int k len - 2; k 0; k--) { printf(%04d, result[k]); } printf(\n);%04d这个格式控制符是精髓它保证每段输出四位不足补零。我第一次写的时候用了%d结果100!的输出中间少了好几个零排查了半天才发现是这里的问题。另外n 0或n 1时结果是 1代码里len初始为 1、result[0] 1正好覆盖不需要额外分支。注意万进制下每段存四位输出时务必用%04d补零这是新手最容易翻车的地方。3.4 性能实测与优化心得我用这套代码在普通笔记本上跑10000!耗时大约 0.3 到 0.5 秒输出约 35660 位数字。如果改成十进制逐位同样规模大概要 2 秒以上。差距主要来自循环次数万进制下内层循环次数是十进制的大约四分之一而且进位处理也更少。进一步优化的话可以考虑用long long做累加、用更大的进制比如十万进制但要注意乘积不能溢出。还有一个技巧是延迟进位内层循环里先不急着取模而是让result[j]暂时存一个较大的数等一轮乘法结束后再统一处理进位。这样能减少取模和除法的次数实测能再快 20% 左右。不过代码会复杂一些初学者建议先用标准写法跑通再考虑优化。4. Python 实现从一行代码到分治优化4.1 内置函数的正确打开方式Python 算阶乘最简单的方式就是math.factorial(n)。这个函数底层是 C 实现的做了不少优化比如对小规模用朴素乘法对大规模用分治策略。我实测math.factorial(10000)几乎是瞬间完成100000大概一两秒1000000需要几分钟。对于绝大多数日常需求直接调用它就够了没必要自己造轮子。import math result math.factorial(1000) print(len(str(result))) # 输出结果的位数这里有个小技巧如果你只关心结果的位数或者末尾零的个数不需要算出完整结果。末尾零的个数等于n!中因子 5 的个数可以用勒让德公式快速算sum(n // 5^k for k in range(1, ...))。这个在组合数学里很常用能省下大量计算。4.2 手写大数乘法的教学价值虽然内置函数够用但如果你想理解大数运算的原理用 Python 手写一遍也很有意义。Python 的列表可以很方便地模拟数组而且不用担心溢出因为 Python 的int本身就是任意精度。下面是一个十进制逐位的实现def factorial_manual(n): result [1] for i in range(2, n 1): carry 0 for j in range(len(result)): prod result[j] * i carry result[j] prod % 10 carry prod // 10 while carry: result.append(carry % 10) carry // 10 return .join(map(str, reversed(result)))这段代码和 C 语言版本逻辑完全一致但因为 Python 的int不会溢出写起来更省心。不过它的速度比math.factorial慢很多算10000!大概要好几秒。所以我的建议是用内置函数拿结果用手写版本学原理两者不矛盾。4.3 分治乘法大规模阶乘的加速思路当n很大时朴素的逐轮相乘会变得很慢因为每轮都要遍历整个结果数组。一个经典的优化是分治乘法把1到n分成两半分别算阶乘再把两个结果相乘。这样做的理由是两个大数相乘时如果规模相近可以用更高效的乘法算法比如 Karatsuba而 Python 的内置乘法正是这么做的。def factorial_divide_conquer(lo, hi): if lo hi: return lo if hi - lo 1: return lo * hi mid (lo hi) // 2 return factorial_divide_conquer(lo, mid) * factorial_divide_conquer(mid 1, hi)这个递归版本算100000!比朴素循环快不少因为乘法次数从 O(n) 次大数乘法降到了 O(log n) 次每次乘法的规模虽然更大但 Python 的内置乘法对大规模有优化。我实测下来分治版本算100000!大概比朴素版本快三到四倍。当然math.factorial内部已经做了类似甚至更好的优化所以自己写分治主要是为了理解思路。4.4 内存与时间的权衡Python 的大整数在内存中是以 30 位为一组存储的具体实现细节随版本变化所以100000!的结果大约有 45 万位十进制数字占用的内存是几兆级别完全可接受。但如果算1000000!结果有 500 多万位内存占用会到几十兆甚至上百兆而且计算时间会显著增加。这时候就要考虑你真的需要完整结果吗如果只需要位数、末尾零个数或者对某个数取模完全可以用数学方法避免完整计算。提示算大阶乘前先问自己“我到底需要结果的哪部分”很多时候不需要完整数字。5. MATLAB 实现符号运算与数组模拟的取舍5.1 符号工具箱的精确计算MATLAB 里最直接的精确阶乘方式是factorial(sym(n))。sym创建符号对象运算过程不丢精度。比如factorial(sym(50))会返回精确的30414093201713378043612608166064768844377641568960512000000000000。这个结果可以直接用于后续符号推导比如求导、化简等。n 50; result factorial(sym(n)); disp(result);但符号运算的代价是速度。我实测factorial(sym(1000))大概要几秒sym(5000)就要几十秒甚至更久。而且符号对象在内存中的表示比普通数值大得多大规模计算容易卡顿。所以sym适合中小规模千位以内的精确计算再大就不太实用了。5.2 双精度数组的局限与判断MATLAB 默认的factorial(n)返回double类型只有约 15 到 16 位有效数字。factorial(22)的结果是1.124000727777608e21虽然显示成科学计数法但实际精度已经丢失。你可以用factorial(22) factorial(sym(22))来验证返回false。所以用double算阶乘超过 20 基本就不可信了。判断什么时候该切换到sym有个简单规则如果n 20且你需要精确结果就必须用sym或自己写数组模拟。如果只是要数量级估计double配合gammaln函数对数伽马函数反而更方便因为log(n!) gammaln(n1)能直接算对数避免溢出。5.3 用数组模拟大数的 MATLAB 写法MATLAB 也可以像 C 语言那样用数组模拟大数思路完全一样。MATLAB 的数组操作是向量化的所以内层乘法可以写成矩阵运算速度比逐元素循环快。下面是一个万进制的实现片段n 1000; result zeros(1, 100000); result(1) 1; len 1; for i 2:n carry 0; for j 1:len prod result(j) * i carry; result(j) mod(prod, 10000); carry floor(prod / 10000); end while carry 0 len len 1; result(len) mod(carry, 10000); carry floor(carry / 10000); end end输出时同样要注意补零MATLAB 里可以用fprintf(%04d, ...)。这个实现比sym快很多算1000!基本瞬间完成算10000!也就一两秒。所以如果你在 MATLAB 里需要算大阶乘又不想依赖符号工具箱数组模拟是很好的选择。5.4 三种语言实现的横向对比与选择建议把三种实现放在一起对比能更清楚地看出各自的定位。C 语言数组模拟最“硬核”代码量最大但可控性最强适合学习和嵌入式场景。Python 内置函数最省事适合快速验证和脚本处理。MATLAB 的sym适合符号推导数组模拟适合数值计算。我个人的工作流是Python 验证 → C 语言复现 → MATLAB 按需选用。这个流程能保证结果正确同时加深对原理的理解。场景推荐方案理由快速拿结果Pythonmath.factorial一行代码底层优化好学习大数原理C 语言万进制数组完全可控理解进位本质符号推导MATLABsym精确且支持后续符号运算大规模数值Python 分治或 C 优化版平衡速度与精度嵌入式/无库C 语言数组不依赖任何外部库6. 常见问题与排查技巧实录6.1 结果末尾一堆零是正常的吗很多人第一次算100!看到末尾一长串零会怀疑是不是算错了。其实这是正常的因为阶乘中因子 2 和 5 配对产生 10而因子 2 远多于 5所以末尾零的个数由因子 5 决定。100!末尾有 24 个零1000!末尾有 249 个零。你可以用勒让德公式验证sum(100 // 5^k for k in range(1, 4)) 20 4 24。所以看到末尾零多不要慌先算一下理论值对不对。6.2 输出中间少零或错位怎么排查这是数组模拟大数时最常见的问题根源几乎总是输出格式没补零。万进制下每段必须输出四位十进制下每位输出一位。如果你用%d而不是%04d中间就会出现错位。排查方法是先算一个小规模比如10! 3628800手动对照输出看是不是每段都正确。另一个可能是数组索引方向搞反了低位在前还是高位在前要统一输出时从高到低遍历。6.3 计算速度突然变慢的原因如果你发现算到某个n之后速度骤降通常有两个原因。一是数组开得太大每轮都遍历整个数组而不是只遍历有效段导致大量无效计算。二是进位处理用了低效的循环比如每次只进一位而不是用整除取余批量处理。解决办法是维护一个len变量记录有效段数并且进位用while循环批量处理。我早期写的一个版本就是因为没维护len算5000!要十几秒加上len之后降到一秒以内。6.4 不同语言结果不一致怎么办如果你用 C 和 Python 算同一个n得到不同结果先检查是不是 C 语言里发生了溢出。int在 32 位系统上最大约 21 亿result[j] * i如果超过这个值就会溢出。解决办法是把result和中间变量都声明为long long或者减小内部进制。另一个可能是 Python 版本用了浮点近似比如math.factorial返回的是精确整数但如果你用了math.gamma就会丢精度。排查时先用小规模n 20对比确认基础逻辑正确再逐步放大。注意C 语言里int溢出是静默的不会报错只会得到错误结果所以大数乘法一定要用足够宽的整型。6.5 常见问题速查表现象可能原因解决办法结果末尾零异常多正常现象因子 5 导致用勒让德公式验证输出中间少零未补零输出用%04d或等价格式结果完全错误整型溢出改用long long或减小进制计算速度慢未维护有效长度用len变量限制循环范围不同语言结果不同精度或溢出问题小规模对比排查MATLAB 结果不精确用了 double改用sym或数组模拟7. 几个我踩过的坑和实用建议第一个坑是数组开太小。我最早用固定大小 1000 的数组算1000!结果越界写入了其他内存程序没崩溃但结果莫名其妙。后来学会用斯特林公式估算位数再留足余量。第二个坑是进位变量没清零。外层循环每轮开始前必须把carry置零否则上一轮的进位会污染下一轮。第三个坑是输出时忘了反转。如果数组是低位在前输出必须从高位到低位遍历否则数字是倒着的。实用建议方面我强烈推荐先用 Python 算一遍标准答案再用 C 或 MATLAB 复现用脚本自动对比结果。这样能快速定位是算法问题还是实现问题。另外如果你只是需要阶乘的近似值别用大数运算直接用lgamma或gammaln算对数又快又稳。最后算大阶乘时记得关注内存1000000!的结果有五百多万位存成字符串也要几兆如果只是中间步骤考虑边算边取模。这个内容后续还可以这样扩展把大数乘法换成快速傅里叶变换FFT实现能进一步加速到接近线性时间复杂度或者把阶乘扩展到双阶乘、多项阶乘等变体思路都是相通的。