在C语言课上，老师刚刚教完循环语句：while(); for(;;);  。然后布置了一个作业：编写一个计算阶乘的程序。

        这个作业说简单可以简单，说难可以难。要简单的话，直接这样写就可以了：

这个程序交作业的话肯定是可以的，毕竟用了for()循环语句，满足要求了。计算方面，能计算个0! 至 12! 。至于再大就不行了，因为超出了int型的存储容量。

        选用能装更大数的数据类型可以在一定程度上，增大其能算到的上限，但增幅不算太大。long long int 撑死就20! ，double 上限170! ，long double 上限1754! 。而且double能存储的有效数字并不多，在存储很大的数时，后面部分全是0，对于我这种有强迫症的人来说，这怎么能忍？于是嘛，便花了10天左右敲出了这个玩意。

看着一大片数字真的爽

(  >д<)ﾉ。

下文大致讲解编写过程

1.特大数据存储

        虽然没有一种数据类型能存储这么大的数据，但是可以用数组来存储。把大数据拆分成各个小段，分块存储进一个数组每一个元素里头，这样就可以达到了存储巨大数据的目的，而且每一个数字都记得清清楚楚。

        最早的时候我是用short int数组来存储的，一个元素存储一个数字，后来我发现这样存储密度太低（0.5个数字/字节），而且计算量很大。后来改用long long int 数组，一个元素存储9个数字，存储密度升为1.125个数字/字节，采用1 000 000 000进制（满10亿进1），这样使得电脑计算量大为减少。

PS：long long int能容纳的最大正整数为9 223 372 036 854 775 807，共19个数字，但是为什么我只装9个呢？主要考虑是当发生999 999 999 * 999 999 999 = 999 999 998 000 000 001时，共18个数字，不会发生溢出。如果装10个数字，即使是unsigned long long int 也溢出了。

        上图为目前我存储结果的方式，定义那里只定义了个指针，还没有赋值其指针指向的内存空间以及对应的空间大小，下文稍后会提到，这里暂时略过。

2.数组内元素运算

        把数拆散了，进行乘法就稍微麻烦了一点，不过还是很容易想到解决办法的，模仿小学学的竖式乘法计算，照着小学学的步骤，让电脑进行相应的运算即可。其中只需补充除法运算进行进位，以及求余运算去掉多余的进位数即可。

        计算n! 就是一个累乘过程，而n一般来说不会太大，把它拆分到一个叫“multiplier”数组里的两个元素就够了，然后让其不停进行乘法即可。由于空间需要，需要多申请3个数组用于存放临时数据，结果存在“cache0”中，过后会转移到“result”的数组上。

        这里也是模仿小学生做竖式计算编写的乘法运行程序，功能也是把两个数相乘，最终也会写入“result”数组中。

3.对数组内操作元素数量控制

        假设数组设置了10个元素，每个元素内装3个数字，但是我只是计算6! （结果=720），结果在数组内是这个样子的：[000][000][000][000][000][000][000][000][000][720]。难不成计算时，要把这十个元素全部历遍么？大部分是对0进行加、乘、除、求余运算，浪费算力浪费时间。虽然说现在电脑都可以到3GHZ或者更高的速度，计算非常快，这点浪费时间可以忽略。但是如果按照题目那样进行百万阶乘，积沙成塔积小成多。本人亲自体验减少这些无用的运算量，在进行大数阶乘时，能显著减少等待时间5分钟以上。

        在计算阶乘之前，程序会先进行预计算，计算n!结果最终有多少个数字，会占用数组多少个元素，再按照其需求，分配数组元素数量，以尽量减低无用的计算。计算n!一共有多少个数字可以由以下公式计出：

        前者是计算n!有多少个数字的公式，对数结果进行向上取整。但是对于电脑来说，本身就不知道n!的数值，所以下面的公式更适合电脑（也不易发生溢出），用循环语句执行即可。对于电脑来说，向下取整的方式更方便进行，于是以向下取整并+1代替向上取整。

        因为数组内一个元素装9个数字，所以电脑主要需要的是结果除以9后的“savenum”。(long int)(....)格式为强制类型转换，一来能进行赋值（因为两者数据类型不同），二来顺便完成了向下取整。

PS：需包含头文件#include<math.h>

4.结果输出

        结果输出很简单，既然知道了数组中那些元素是装了实际的数字，哪些是无用的“0”，那就直接读取“savenum”内的数，并倒序输出。

PS：输出格式上要调整为"%09lld"，即使数组内全是“0”，也要一个不漏输出。

5.栈溢出——向堆内存要

        在我写旧版计算器中，当计算到2100!以后，计算会莫名终止，然后一直无响应。那是因为数组过大，发生了栈溢出。栈溢出后，程序就崩溃停止了。

        查资料可以知道，其实在一般的C语言程序中，程序分配的栈内存其实很少，一般在1MB左右，当数据过大时，栈就发生溢出了。还好，C语言中有个“malloc”函数，可以自定义向堆内存分配内存空间。

PS：需要头文件#include<stdlib.h>或#include<malloc.h>

        sizeof()函数返回该数据类型所占用的内存空间，单位是字节。自然sizeof(long long int)返回的值是：8 。malloc()括号内填写的是需要分配的内存空间，单位是字节。前文提到“savenum”变量内的数是计算n!需要的数组元素数，刚好这里派上用场。两者一相乘就得到所需的内存大小空间了。result数组所占用的内存大小，会根据n!的大小自动调节，而不是在刚刚开始定义那里就固定死了。malloc()返回的是一个指针，是一个内存地址，指向内存中该内存空间的首地址，指针需进行强制类型转换后，付给指针变量。

图中“result”是一个二维数组，通俗讲是个result[ ][ ];，通过如图进行分配内存空间。

分配完成后，必须进行if检查其指针变量内的指针是否为空。因为内存分配失败后，malloc()返回的是一个空指针。所以必须进行检查，因为一旦分配失败，后面的代码执行会造成程序崩溃。

        内存分配成功后，必须对其内存空间进行初始化处理（全部写0）。因为刚刚获得到手的内存，里面很有可能有别的程序运行完后，留下的许多垃圾数据在内存中，这些数据是随机的，有可能会对后面的运行造成影响，所以必须写0覆盖。

        当一切计算完成，结果输出完毕后，就可以拍屁股走人了？不！刚刚向堆内存分配的，必须释放还回去。否则这些内存将一直占用，如果下一批计算进行，新的内存分配会覆盖掉原来的内存地址，造成这些内存将永远不能释放，引发内存泄露，导致整个系统的内存越来越少，最后崩溃。

PS：现在windows系统对这处理比较完善了，当该进程被关掉后，windows会找到这些内存并且释放掉。但这是整个阶乘计算器被关掉后回收的，如果运行期间将无法回收。所以写代码时必须主动去释放这些内存。

番外：来计算个2 000 000 000! 吧

emmm，也许需要个2TB内存服务器才能算了。hhhhhh

_(:з」∠)_

        哎等等，有没有留意到，即使内存分配失败了，在退出计算前，也要把分配成功的释放掉。不放掉的话，怎么玩呢？

6.调用多线程进行运算

        计算10000以内的阶乘，速度还是很快的，但是到达100000的阶乘，明显感觉速度慢下来了，这时候看看这个图……

        拥有一个12核24线程的CPU，不调动全核心进行运算怎么可以？全核出击，攻下百万阶乘！

        多线程，能显著提高并行运算的速度，相当于有多个人同时完成一份工作。分配也很简单，假设10条线程运行，计算10000!，那就把10000分成10份。一条线程负责计算1乘到1000，一条负责计算1001乘到2000……，最后一条负责从9001乘到100000，十条线程一起运算完成后，再把结果合并起来，得出总结果。

PS：需要头文件#include<pthread.h>

 上图中即启动了一个子线程，如果想更多的话，多抄几句就是，记得改“th1”。

也可以使用for语句，控制其调用线程的数量。别忘了后面要记得回收。

下面是一张极其舒适的图

( >д<)ﾉ

7.输出结果到.txt

当计算100000的阶乘后，数字已经多到窗口不能容纳了，在计算1000000的阶乘中，结果有4/5的数字被吞了。所以需要一个导出到.txt文档以输出结果。

8.主函数

        我倒是把计算的主要任务都扔子函数里去了，主函数也就一个用户界面差不多。没什么好看的，看到啥了也别说。

_(¦3」∠)_

9.冲击百万阶乘

        下面就是见证1 000 000!的结果了。数字过多，也就图个乐，文章就这样吧。qwq

↑可能还需要50张左右这样的截图，才能把结果全部截完。