【C语言】百万阶乘计算器

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

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

计算n!

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


各数据类型占用内存空间以及表示的数据范围

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

计算2333!

看着一大片数字真的爽

(  >д<)ノ。

下文大致讲解编写过程

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! 吧

计算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语句,控制其调用线程的数量。别忘了后面要记得回收。

子线程回收


被子线程调用的指针函数

下面是一张极其舒适的图

( >д<)ノ

CPU使用率:100%


7.输出结果到.txt

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

导出到 .txt 代码


8.主函数

主函数部分

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

_(¦3」∠)_


9.冲击百万阶乘

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

1 000 000!计算过程

1 000 000! 部分结果

1 000 000! 结果的冰山一角

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


本文为我原创

本文禁止转载或摘编

-- --
  • 投诉或建议
评论