? ? ? ? 在C語言課上，老師剛剛教完循環(huán)語句：while(); for(;;); ?。然后布置了一個(gè)作業(yè)：編寫一個(gè)計(jì)算階乘的程序。

? ? ? ? 這個(gè)作業(yè)說簡單可以簡單，說難可以難。要簡單的話，直接這樣寫就可以了：

這個(gè)程序交作業(yè)的話肯定是可以的，畢竟用了for()循環(huán)語句，滿足要求了。計(jì)算方面，能計(jì)算個(gè)0! 至 12! 。至于再大就不行了，因?yàn)槌隽薸nt型的存儲(chǔ)容量。

? ? ? ? 選用能裝更大數(shù)的數(shù)據(jù)類型可以在一定程度上，增大其能算到的上限，但增幅不算太大。long long int 撐死就20! ，double 上限170! ，long double 上限1754! 。而且double能存儲(chǔ)的有效數(shù)字并不多，在存儲(chǔ)很大的數(shù)時(shí)，后面部分全是0，對(duì)于我這種有強(qiáng)迫癥的人來說，這怎么能忍？于是嘛，便花了10天左右敲出了這個(gè)玩意。

看著一大片數(shù)字真的爽

( ?>д<)?。

下文大致講解編寫過程

1.特大數(shù)據(jù)存儲(chǔ)

? ? ? ? 雖然沒有一種數(shù)據(jù)類型能存儲(chǔ)這么大的數(shù)據(jù)，但是可以用數(shù)組來存儲(chǔ)。把大數(shù)據(jù)拆分成各個(gè)小段，分塊存儲(chǔ)進(jìn)一個(gè)數(shù)組每一個(gè)元素里頭，這樣就可以達(dá)到了存儲(chǔ)巨大數(shù)據(jù)的目的，而且每一個(gè)數(shù)字都記得清清楚楚。

? ? ? ? 最早的時(shí)候我是用short int數(shù)組來存儲(chǔ)的，一個(gè)元素存儲(chǔ)一個(gè)數(shù)字，后來我發(fā)現(xiàn)這樣存儲(chǔ)密度太低（0.5個(gè)數(shù)字/字節(jié)），而且計(jì)算量很大。后來改用long long int 數(shù)組，一個(gè)元素存儲(chǔ)9個(gè)數(shù)字，存儲(chǔ)密度升為1.125個(gè)數(shù)字/字節(jié)，采用1 000 000 000進(jìn)制（滿10億進(jìn)1），這樣使得電腦計(jì)算量大為減少。

PS：long long int能容納的最大正整數(shù)為9 223 372 036 854 775 807，共19個(gè)數(shù)字，但是為什么我只裝9個(gè)呢？主要考慮是當(dāng)發(fā)生999 999 999 * 999 999 999 = 999 999 998 000 000 001時(shí)，共18個(gè)數(shù)字，不會(huì)發(fā)生溢出。如果裝10個(gè)數(shù)字，即使是unsigned long long int 也溢出了。

? ? ? ? 上圖為目前我存儲(chǔ)結(jié)果的方式，定義那里只定義了個(gè)指針，還沒有賦值其指針指向的內(nèi)存空間以及對(duì)應(yīng)的空間大小，下文稍后會(huì)提到，這里暫時(shí)略過。

2.數(shù)組內(nèi)元素運(yùn)算

? ? ? ? 把數(shù)拆散了，進(jìn)行乘法就稍微麻煩了一點(diǎn)，不過還是很容易想到解決辦法的，模仿小學(xué)學(xué)的豎式乘法計(jì)算，照著小學(xué)學(xué)的步驟，讓電腦進(jìn)行相應(yīng)的運(yùn)算即可。其中只需補(bǔ)充除法運(yùn)算進(jìn)行進(jìn)位，以及求余運(yùn)算去掉多余的進(jìn)位數(shù)即可。

? ? ? ? 計(jì)算n! 就是一個(gè)累乘過程，而n一般來說不會(huì)太大，把它拆分到一個(gè)叫“multiplier”數(shù)組里的兩個(gè)元素就夠了，然后讓其不停進(jìn)行乘法即可。由于空間需要，需要多申請3個(gè)數(shù)組用于存放臨時(shí)數(shù)據(jù)，結(jié)果存在“cache0”中，過后會(huì)轉(zhuǎn)移到“result”的數(shù)組上。

? ? ? ? 這里也是模仿小學(xué)生做豎式計(jì)算編寫的乘法運(yùn)行程序，功能也是把兩個(gè)數(shù)相乘，最終也會(huì)寫入“result”數(shù)組中。

3.對(duì)數(shù)組內(nèi)操作元素?cái)?shù)量控制

? ? ? ? 假設(shè)數(shù)組設(shè)置了10個(gè)元素，每個(gè)元素內(nèi)裝3個(gè)數(shù)字，但是我只是計(jì)算6! （結(jié)果=720），結(jié)果在數(shù)組內(nèi)是這個(gè)樣子的：[000][000][000][000][000][000][000][000][000][720]。難不成計(jì)算時(shí)，要把這十個(gè)元素全部歷遍么？大部分是對(duì)0進(jìn)行加、乘、除、求余運(yùn)算，浪費(fèi)算力浪費(fèi)時(shí)間。雖然說現(xiàn)在電腦都可以到3GHZ或者更高的速度，計(jì)算非?？?，這點(diǎn)浪費(fèi)時(shí)間可以忽略。但是如果按照題目那樣進(jìn)行百萬階乘，積沙成塔積小成多。本人親自體驗(yàn)減少這些無用的運(yùn)算量，在進(jìn)行大數(shù)階乘時(shí)，能顯著減少等待時(shí)間5分鐘以上。

? ? ? ? 在計(jì)算階乘之前，程序會(huì)先進(jìn)行預(yù)計(jì)算，計(jì)算n!結(jié)果最終有多少個(gè)數(shù)字，會(huì)占用數(shù)組多少個(gè)元素，再按照其需求，分配數(shù)組元素?cái)?shù)量，以盡量減低無用的計(jì)算。計(jì)算n!一共有多少個(gè)數(shù)字可以由以下公式計(jì)出：

? ? ? ? 前者是計(jì)算n!有多少個(gè)數(shù)字的公式，對(duì)數(shù)結(jié)果進(jìn)行向上取整。但是對(duì)于電腦來說，本身就不知道n!的數(shù)值，所以下面的公式更適合電腦（也不易發(fā)生溢出），用循環(huán)語句執(zhí)行即可。對(duì)于電腦來說，向下取整的方式更方便進(jìn)行，于是以向下取整并+1代替向上取整。

? ? ? ? 因?yàn)閿?shù)組內(nèi)一個(gè)元素裝9個(gè)數(shù)字，所以電腦主要需要的是結(jié)果除以9后的“savenum”。(long int)(....)格式為強(qiáng)制類型轉(zhuǎn)換，一來能進(jìn)行賦值（因?yàn)閮烧邤?shù)據(jù)類型不同），二來順便完成了向下取整。

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

4.結(jié)果輸出

? ? ? ? 結(jié)果輸出很簡單，既然知道了數(shù)組中那些元素是裝了實(shí)際的數(shù)字，哪些是無用的“0”，那就直接讀取“savenum”內(nèi)的數(shù)，并倒序輸出。

PS：輸出格式上要調(diào)整為"%09lld"，即使數(shù)組內(nèi)全是“0”，也要一個(gè)不漏輸出。

5.棧溢出——向堆內(nèi)存要

? ? ? ? 在我寫舊版計(jì)算器中，當(dāng)計(jì)算到2100!以后，計(jì)算會(huì)莫名終止，然后一直無響應(yīng)。那是因?yàn)閿?shù)組過大，發(fā)生了棧溢出。棧溢出后，程序就崩潰停止了。

? ? ? ? 查資料可以知道，其實(shí)在一般的C語言程序中，程序分配的棧內(nèi)存其實(shí)很少，一般在1MB左右，當(dāng)數(shù)據(jù)過大時(shí)，棧就發(fā)生溢出了。還好，C語言中有個(gè)“malloc”函數(shù)，可以自定義向堆內(nèi)存分配內(nèi)存空間。

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

? ? ? ? sizeof()函數(shù)返回該數(shù)據(jù)類型所占用的內(nèi)存空間，單位是字節(jié)。自然sizeof(long long int)返回的值是：8 。malloc()括號(hào)內(nèi)填寫的是需要分配的內(nèi)存空間，單位是字節(jié)。前文提到“savenum”變量內(nèi)的數(shù)是計(jì)算n!需要的數(shù)組元素?cái)?shù)，剛好這里派上用場。兩者一相乘就得到所需的內(nèi)存大小空間了。result數(shù)組所占用的內(nèi)存大小，會(huì)根據(jù)n!的大小自動(dòng)調(diào)節(jié)，而不是在剛剛開始定義那里就固定死了。malloc()返回的是一個(gè)指針，是一個(gè)內(nèi)存地址，指向內(nèi)存中該內(nèi)存空間的首地址，指針需進(jìn)行強(qiáng)制類型轉(zhuǎn)換后，付給指針變量。

圖中“result”是一個(gè)二維數(shù)組，通俗講是個(gè)result[ ][ ];，通過如圖進(jìn)行分配內(nèi)存空間。

分配完成后，必須進(jìn)行if檢查其指針變量內(nèi)的指針是否為空。因?yàn)閮?nèi)存分配失敗后，malloc()返回的是一個(gè)空指針。所以必須進(jìn)行檢查，因?yàn)橐坏┓峙涫?，后面的代碼執(zhí)行會(huì)造成程序崩潰。

? ? ? ? 內(nèi)存分配成功后，必須對(duì)其內(nèi)存空間進(jìn)行初始化處理（全部寫0）。因?yàn)閯倓偒@得到手的內(nèi)存，里面很有可能有別的程序運(yùn)行完后，留下的許多垃圾數(shù)據(jù)在內(nèi)存中，這些數(shù)據(jù)是隨機(jī)的，有可能會(huì)對(duì)后面的運(yùn)行造成影響，所以必須寫0覆蓋。

? ? ? ? 當(dāng)一切計(jì)算完成，結(jié)果輸出完畢后，就可以拍屁股走人了？不！剛剛向堆內(nèi)存分配的，必須釋放還回去。否則這些內(nèi)存將一直占用，如果下一批計(jì)算進(jìn)行，新的內(nèi)存分配會(huì)覆蓋掉原來的內(nèi)存地址，造成這些內(nèi)存將永遠(yuǎn)不能釋放，引發(fā)內(nèi)存泄露，導(dǎo)致整個(gè)系統(tǒng)的內(nèi)存越來越少，最后崩潰。

PS：現(xiàn)在windows系統(tǒng)對(duì)這處理比較完善了，當(dāng)該進(jìn)程被關(guān)掉后，windows會(huì)找到這些內(nèi)存并且釋放掉。但這是整個(gè)階乘計(jì)算器被關(guān)掉后回收的，如果運(yùn)行期間將無法回收。所以寫代碼時(shí)必須主動(dòng)去釋放這些內(nèi)存。

番外：來計(jì)算個(gè)2 000 000 000!?吧

emmm，也許需要個(gè)2TB內(nèi)存服務(wù)器才能算了。hhhhhh

_(:з」∠)_

? ? ? ? 哎等等，有沒有留意到，即使內(nèi)存分配失敗了，在退出計(jì)算前，也要把分配成功的釋放掉。不放掉的話，怎么玩呢？

6.調(diào)用多線程進(jìn)行運(yùn)算

? ? ? ? 計(jì)算10000以內(nèi)的階乘，速度還是很快的，但是到達(dá)100000的階乘，明顯感覺速度慢下來了，這時(shí)候看看這個(gè)圖……

? ? ? ? 擁有一個(gè)12核24線程的CPU，不調(diào)動(dòng)全核心進(jìn)行運(yùn)算怎么可以？全核出擊，攻下百萬階乘！

? ? ? ? 多線程，能顯著提高并行運(yùn)算的速度，相當(dāng)于有多個(gè)人同時(shí)完成一份工作。分配也很簡單，假設(shè)10條線程運(yùn)行，計(jì)算10000!，那就把10000分成10份。一條線程負(fù)責(zé)計(jì)算1乘到1000，一條負(fù)責(zé)計(jì)算1001乘到2000……，最后一條負(fù)責(zé)從9001乘到100000，十條線程一起運(yùn)算完成后，再把結(jié)果合并起來，得出總結(jié)果。

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

?上圖中即啟動(dòng)了一個(gè)子線程，如果想更多的話，多抄幾句就是，記得改“th1”。

也可以使用for語句，控制其調(diào)用線程的數(shù)量。別忘了后面要記得回收。

下面是一張極其舒適的圖

( >д<)?

7.輸出結(jié)果到.txt

當(dāng)計(jì)算100000的階乘后，數(shù)字已經(jīng)多到窗口不能容納了，在計(jì)算1000000的階乘中，結(jié)果有4/5的數(shù)字被吞了。所以需要一個(gè)導(dǎo)出到.txt文檔以輸出結(jié)果。

8.主函數(shù)

? ? ? ? 我倒是把計(jì)算的主要任務(wù)都扔子函數(shù)里去了，主函數(shù)也就一個(gè)用戶界面差不多。沒什么好看的，看到啥了也別說。

_(|3」∠)_

9.沖擊百萬階乘

? ? ? ? 下面就是見證1 000 000!的結(jié)果了。數(shù)字過多，也就圖個(gè)樂，文章就這樣吧。qwq

↑可能還需要50張左右這樣的截圖，才能把結(jié)果全部截完。