大數(shù)運(yùn)算實(shí)現(xiàn)的相關(guān)技術(shù)研究

余發(fā)高，胡 鳴

(武漢紡織大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北 武漢 430200)

大數(shù)運(yùn)算目前在信息安全、數(shù)字圖像、大數(shù)據(jù)挖掘等領(lǐng)域應(yīng)用比較廣泛，甚至在研究星體計(jì)算中需要精確到小數(shù)點(diǎn)指定位數(shù)，將誤差降低到最小。目前JAVA在大數(shù)運(yùn)算方面做了一些相關(guān)的研究，但在算法上還需要進(jìn)一步的優(yōu)化。本文針對(duì)C語(yǔ)言在大數(shù)運(yùn)算方面提出了大數(shù)運(yùn)算模型以及大數(shù)運(yùn)算算法，與JAVA大數(shù)加減乘除相比較，大數(shù)加法和減法在計(jì)算效率上要更快；大數(shù)乘法速度是JAVA計(jì)算的2到3倍；大數(shù)除法能保留小數(shù)點(diǎn)9位數(shù)。

1 大數(shù)計(jì)算的設(shè)計(jì)

1.1 大數(shù)計(jì)算框架

提出了DLNC（Design of Large Number Computing）模型（見圖1），通過(guò)此模型當(dāng)輸入數(shù)據(jù)存儲(chǔ)超過(guò)了字長(zhǎng)時(shí)，動(dòng)態(tài)調(diào)整字長(zhǎng)來(lái)存儲(chǔ)；當(dāng)存儲(chǔ)沒有操出字長(zhǎng)就不需要調(diào)整。然后參與計(jì)算，計(jì)算結(jié)果存儲(chǔ)過(guò)程中，如果檢測(cè)出超出字長(zhǎng)，再次調(diào)整字長(zhǎng)，最后存儲(chǔ)結(jié)果，然后進(jìn)行輸出結(jié)果。此模型主要為解決大數(shù)計(jì)算而提出，在輸入過(guò)程中如果超出了存儲(chǔ)的字長(zhǎng)，就來(lái)動(dòng)態(tài)的增加字長(zhǎng)；在計(jì)算結(jié)果存儲(chǔ)過(guò)程中如果超出了字長(zhǎng)，用同樣的方法來(lái)增加字長(zhǎng)進(jìn)行存儲(chǔ)，從而突破了普通計(jì)算字長(zhǎng)的限制，能夠?qū)崿F(xiàn)大數(shù)基本的計(jì)算。

圖1 大數(shù)計(jì)算框架圖

1.2 大數(shù)計(jì)算數(shù)表示的的幾種方法

（1）存放大數(shù)可以采取用鏈表形式來(lái)存貯的，由于要在計(jì)算中會(huì)用到從高位開始計(jì)算以及從低位開始計(jì)算數(shù)值的兩種情況，所以我們將鏈表定義為雙向鏈表，其中一個(gè)指向后的數(shù)據(jù)，另一個(gè)指向一個(gè)單元來(lái)存儲(chǔ)數(shù)據(jù)，一個(gè)指針指向前方的數(shù)據(jù)。

（2）在計(jì)算機(jī)中，數(shù)的表示可以分為兩種，一種是用二進(jìn)制來(lái)表示，一種是用十進(jìn)制來(lái)表示。用長(zhǎng)為len的short型數(shù)組或者long型數(shù)組甚至longlong數(shù)組來(lái)表示大數(shù)，可以采用權(quán)從大到小的順序來(lái)存放，大數(shù)表示的形式如下：

也可以用十進(jìn)制的方式來(lái)表示大數(shù)如下：

（3）大數(shù)的表示也可以用大尾序或者小尾序的方式。大尾序就是低位字節(jié)排放在內(nèi)存的高端，高位字節(jié)排放在內(nèi)存的低端；小尾序就是高位字節(jié)排放在內(nèi)存的高端，低位字節(jié)排放在內(nèi)存的低端。

（4）用不完全精度的方法來(lái)表示大數(shù)。有時(shí)計(jì)算的結(jié)果需要精確到有限的位數(shù)，沒必要全部計(jì)算出來(lái)，這樣可以節(jié)省計(jì)算的時(shí)間。不完全精度的方法來(lái)表示大數(shù)，除了用數(shù)組來(lái)存儲(chǔ)有限數(shù)值外，還需要一個(gè)數(shù)來(lái)表示有效數(shù)字的權(quán)值。

（5）定義結(jié)構(gòu)體成員部分來(lái)表示大數(shù)，包含以下幾個(gè)部分：整數(shù)部分的位數(shù)以及浮點(diǎn)部分的位數(shù)，要定義字符數(shù)組表示為整數(shù)部分以及字符數(shù)組表示為浮點(diǎn)部分，幵且要定義表示整型和浮點(diǎn)數(shù)字符型數(shù)組大小，可以根據(jù)需要自行修改宏定義里面的內(nèi)容，以修改數(shù)組大小。幵且要定義字符型數(shù)據(jù)的符號(hào)位，還要定義字符型表示無(wú)窮，對(duì)計(jì)算錯(cuò)誤可以做一些函數(shù)內(nèi)部處理。

（6）可以使用多個(gè)或者多維數(shù)組的方法以及字符串形式來(lái)表示大數(shù)。

（7）多精度利用固定精度數(shù)據(jù)類型創(chuàng)建和操縱能夠表示大數(shù)的多精度整數(shù)。

1.3 大數(shù)計(jì)算處理溢出的方法

（1）在實(shí)際分配內(nèi)存空間時(shí)，對(duì)數(shù)據(jù)的輸入與輸出可以動(dòng)態(tài)的調(diào)整字符數(shù)組或者字符串的長(zhǎng)度來(lái)突破字長(zhǎng)的限制，從而可以解決大數(shù)數(shù)據(jù)溢出的問(wèn)題。

（2）以字符串形式來(lái)存儲(chǔ)大數(shù)，通過(guò)單個(gè)的字符得到對(duì)應(yīng)的十進(jìn)制數(shù)，從而可以進(jìn)行計(jì)算。

（3）在java中一個(gè)類BigInteger表示大整數(shù)類，另一個(gè)類BigDecimal表示大浮點(diǎn)數(shù)類，理論上能夠表示無(wú)限大的數(shù)，只要計(jì)算機(jī)內(nèi)存足夠大。

上面的方法都是用軟件的方法來(lái)解決大數(shù)溢出的相關(guān)問(wèn)題，但是如果我們從硬件的角度來(lái)考慮的話，也就是要提高硬件的設(shè)備，我們可以采用64位或者128位甚至更高位的字長(zhǎng)的計(jì)算機(jī)來(lái)解決堆棧溢出和計(jì)數(shù)器溢出的相關(guān)問(wèn)題，但是目前來(lái)說(shuō)，生產(chǎn)的成本以及技術(shù)的成本過(guò)高，現(xiàn)階段可能無(wú)法實(shí)現(xiàn)，但是隨著計(jì)算機(jī)的發(fā)展，大數(shù)據(jù)的興起，到那時(shí)這些問(wèn)題都將迎刃而解，但這里還是從軟件方面來(lái)考慮如何解決大數(shù)溢出的根本問(wèn)題。

2 大數(shù)基本運(yùn)算設(shè)計(jì)

2.1 大數(shù)加法和減法的運(yùn)算設(shè)計(jì)

這里首先提出ADLNO（Algorithmic Design of Large Number Operation）大數(shù)運(yùn)算算法設(shè)計(jì)模型，這個(gè)模型適用于大數(shù)加法、大數(shù)減法、大數(shù)除法、大數(shù)乘法的運(yùn)算。大數(shù)加法運(yùn)算是相對(duì)簡(jiǎn)單的一種算法，實(shí)質(zhì)就是選擇兩個(gè)整數(shù)位數(shù)較長(zhǎng)的那個(gè)數(shù)字作為加法運(yùn)算的循環(huán)變量，從整數(shù)的最低位開始計(jì)算起，把兩個(gè)操作數(shù)根據(jù)其相對(duì)應(yīng)位置的數(shù)字進(jìn)行加法操作，然后加上前一位的進(jìn)位，判斷此時(shí)是否會(huì)向前一位進(jìn)位，如有進(jìn)位，則把進(jìn)位值賦予1（進(jìn)位制不可能是1以上的數(shù)字，因?yàn)閷?duì)應(yīng)位置的數(shù)相加大小不會(huì)超過(guò)20），此時(shí)如果存在進(jìn)位，將得到的對(duì)應(yīng)位置的和除以10（因?yàn)槭鞘M(jìn)制的加法計(jì)算）進(jìn)行取整，就會(huì)得到本位應(yīng)該輸出的和了。否則，沒有進(jìn)位的情況，則將得到的對(duì)應(yīng)位置的和同樣除以 10進(jìn)行取余數(shù)，就會(huì)得到本位應(yīng)該輸出的和了。循環(huán)上面的操作直至最高位，即得到最后的結(jié)果。大數(shù)的減法，因?yàn)槭褂昧私Y(jié)構(gòu)體對(duì)操作數(shù)進(jìn)行了數(shù)字存儲(chǔ)，也會(huì)和之前一樣分割大數(shù)的整數(shù)部分和小數(shù)部分。在處理整數(shù)部分的減法時(shí)，也是從兩個(gè)操作數(shù)的低位開始計(jì)算起，判斷兩個(gè)操作數(shù)的關(guān)系，看看兩個(gè)操作數(shù)的長(zhǎng)度，如果兩個(gè)操作數(shù)相等則直接返回結(jié)果 0，如果兩個(gè)操作數(shù)不等，繼續(xù)比較兩個(gè)數(shù)的長(zhǎng)度。如果被減數(shù)的位數(shù)長(zhǎng)度大于減數(shù)的位數(shù)長(zhǎng)度，則正常的用被減數(shù)減去減數(shù)得到差。如果減數(shù)的位數(shù)長(zhǎng)度大于被減數(shù)的位數(shù)長(zhǎng)度，則用減數(shù)減去被減數(shù)，最后得到的差加上負(fù)號(hào)。在每一項(xiàng)相減時(shí)，需要注意每一位的借位。如果前一位有借位，計(jì)算本位時(shí)應(yīng)該減去結(jié)尾，沒有借位則直接減，再去判段本位是否需要借位，如果需要借位，則將借位置于1，否則置為0。之后就是不斷地重復(fù)循環(huán)以上步驟，直至見到最高位得到最后的差。在處理小數(shù)部分和整數(shù)部分基本相同，只需從低位減到高位，其他步驟與整數(shù)部分一致。

有關(guān)小數(shù)部分的加法減法運(yùn)算，則與整數(shù)加法減法運(yùn)算相類似。以小數(shù)位數(shù)較長(zhǎng)的部分作為循環(huán)變量，從低位向高位不斷地一位一位循環(huán)向前加，得到最終結(jié)果。由于加法和減法算法類似，下面是加法偽代碼部分：

2.2 大數(shù)乘法的運(yùn)算設(shè)計(jì)

關(guān)于大數(shù)乘法的思路，首先大數(shù)乘法同樣是從操作數(shù)的低位開始計(jì)算起，用一個(gè)數(shù)的所有位去乘上另一個(gè)數(shù)的最低位，得到結(jié)果再繼續(xù)向前進(jìn)一位，進(jìn)行計(jì)算另外一個(gè)數(shù)的前一位與第一個(gè)操作數(shù)的所有位相乘。通過(guò)這樣反復(fù)循環(huán)，重復(fù)計(jì)算到至高位，把它們加起來(lái)就是最后乘法的積了。這里因?yàn)槊恳淮蔚某朔ǘ紩?huì)用到一個(gè)結(jié)構(gòu)體變量對(duì)這個(gè)臨時(shí)的積進(jìn)行存儲(chǔ)，如果位數(shù)比較多，就需要大量的結(jié)構(gòu)體變量用了進(jìn)行存儲(chǔ)這些臨時(shí)的變量。為了減少開銷，我們先將一個(gè)臨時(shí)變量存在一個(gè)結(jié)構(gòu)體變量中，把這個(gè)臨時(shí)變量與下個(gè)臨時(shí)變量相加存在另外一個(gè)結(jié)構(gòu)體變量中，后面的臨時(shí)變量再與這個(gè)相加時(shí)，再存到第一個(gè)結(jié)構(gòu)體中，這樣反復(fù)存儲(chǔ)計(jì)算實(shí)際上只使用了兩個(gè)結(jié)構(gòu)體變量進(jìn)行存儲(chǔ)數(shù)據(jù)，大大減少了對(duì)空間的開銷。

2.3 大數(shù)除法的運(yùn)算設(shè)計(jì)

當(dāng)被除數(shù)除不了時(shí)候，需要被除數(shù)補(bǔ)零直至能除除數(shù)，也要除到規(guī)定的小數(shù)位數(shù)。從高位向低位減，做減時(shí)以被除數(shù)長(zhǎng)度為單位，從高位取出大于被除數(shù)的字符串（被除數(shù)），然后將原除數(shù)乘以一個(gè)權(quán)值（小于10）得到一個(gè)不大于被除數(shù)的新的被除數(shù)，再用被除數(shù)減去新的除數(shù)，這個(gè)權(quán)值就是結(jié)果，余數(shù)從剩下的被除數(shù)高位再取出幾位做補(bǔ)位，這樣循環(huán)此步操作，直到對(duì)應(yīng)小數(shù)返回為止。進(jìn)行浮點(diǎn)數(shù)除法運(yùn)算時(shí)，需要轉(zhuǎn)化為整數(shù)除，得到結(jié)果后再回歸小數(shù)點(diǎn)。

3 性能分析與實(shí)驗(yàn)

3.1 加法和減法運(yùn)算的性能分析

圖2 大數(shù)加法示意圖

從圖2可以看出，對(duì)于c大數(shù)加法從16位，32位，64位，128位，256位，512位與java大數(shù)加法從16位，32位，64位，128位，256位，512位相比較，c大數(shù)加法用的時(shí)間顯然要少，但是從1024位開始，一直到8192位，相同的大數(shù)，c用的時(shí)間要比java用的時(shí)間多。可以看出1024位是c和java大數(shù)加法的速度快慢的一個(gè)轉(zhuǎn)折點(diǎn)。從而可以得出，c在計(jì)算1024位大數(shù)的加法優(yōu)勢(shì)挺明顯，但要計(jì)算1024位以上的大數(shù)加法卻遠(yuǎn)不如java速度。由于大數(shù)減法算法和加法算法類似，通過(guò)實(shí)驗(yàn)得出和加法類似的結(jié)論。

3.2 乘法運(yùn)算的性能分析

圖3 大數(shù)乘法示意圖

從圖3可以看出，無(wú)論c從16一直取到1024位，再?gòu)?024位取到8192位，同樣的數(shù)據(jù)所用的時(shí)間一直遠(yuǎn)小于java所用的時(shí)間，從上面的圖表可以看出：從16位，32位，64位，c所用的時(shí)間是java所用的時(shí)間的二分之一；同樣的128位大數(shù)，java用的時(shí)間大約是c用的時(shí)間的3倍，當(dāng)256位大數(shù)時(shí)，java用的時(shí)間是c用的時(shí)間的5倍；當(dāng)512位大數(shù)時(shí)，java用的時(shí)間是c用的時(shí)間的9倍多；當(dāng)1024位大數(shù)時(shí)，java用的時(shí)間是c用的時(shí)間的9倍多；當(dāng)2048位大數(shù)時(shí)，java用的時(shí)間是c用的時(shí)間的8倍多；當(dāng)4096位大數(shù)時(shí)，java用的時(shí)間是c用的時(shí)間的6倍多；當(dāng)8192位大數(shù)時(shí)，java用的時(shí)間是c用的時(shí)間的5倍多；從上面的數(shù)據(jù)分析可以看出，從16位大數(shù)，一直到1024位大數(shù)，java所用的時(shí)間在成倍數(shù)的增加，也就是c所用的時(shí)間成倍縮小；從1024位一直到8192位java所用的時(shí)間在成倍數(shù)減小，也就是c所用的時(shí)間成倍數(shù)增加。綜上所述c大數(shù)乘法從16位一直到8192位所用的時(shí)間和java所用的時(shí)間相比較，一直很少，也就是說(shuō)c在大數(shù)乘法上，速度一直比java要快的多。

3.3 除法運(yùn)算的性能分析

本文基于C語(yǔ)言大數(shù)除法構(gòu)造函數(shù)時(shí)，通過(guò)自己構(gòu)造函數(shù)，以及設(shè)計(jì)除法的算法，通過(guò)計(jì)算可以獲得除法的結(jié)果，幵且能保留小數(shù)點(diǎn)9位數(shù)值，但通過(guò)java計(jì)算除法時(shí)，發(fā)現(xiàn)java除法是取商的，也就是無(wú)法取到小數(shù)點(diǎn)，由于計(jì)算結(jié)果的不同，c語(yǔ)言大數(shù)除法無(wú)法和java大數(shù)除法在時(shí)間上進(jìn)行比較。但通過(guò)實(shí)驗(yàn)我們發(fā)現(xiàn)，c語(yǔ)言構(gòu)造的大數(shù)除法函數(shù)能夠計(jì)算出結(jié)果，幵且能夠保留小數(shù)點(diǎn)后面的9位數(shù)值，當(dāng)然對(duì)于大數(shù)的運(yùn)算能夠根據(jù)實(shí)際需要設(shè)置小數(shù)點(diǎn)后面的數(shù)值也是今后的研究中需要改進(jìn)的，但目前能夠精確到小數(shù)點(diǎn)9位數(shù)值。

4 總結(jié)

本次所設(shè)計(jì)c語(yǔ)言大數(shù)運(yùn)算加法、減法、乘法、除法的函數(shù)以及算法，總體就是通過(guò)模擬筆算的過(guò)程來(lái)實(shí)現(xiàn)的大數(shù)運(yùn)算，同時(shí)通過(guò)設(shè)計(jì)時(shí)間函數(shù)與對(duì)應(yīng)的java大數(shù)運(yùn)算進(jìn)行比較，C語(yǔ)言在大數(shù)加法和減法計(jì)算過(guò)程要比java大數(shù)加法和減法要慢，乘法計(jì)算的速度要比java快的很多，除法能夠計(jì)算出結(jié)果幵且能保留小數(shù)點(diǎn)9位數(shù)字。