柴 君

天津電子信息職業(yè)技術(shù)學(xué)院，天津 300350

0 引言

首先，我們來閱讀如下簡單C語言程序:

很顯然，如果是在Turbo C環(huán)境下運行，則輸出的結(jié)果是字符串no。出現(xiàn)這種結(jié)果的原因也不是很難分析:由于計算機給任何數(shù)據(jù)分配的內(nèi)存空間都是有限的，它不能直接存放任意大或者任意精度的數(shù)據(jù)。但是在計算機應(yīng)用中，尤其是信息安全密碼學(xué)和科學(xué)計算中，大數(shù)運算和高精度運算有著普遍的需求。在這種矛盾中，對超過范圍的數(shù)據(jù)（這里的范圍包括大小和精度:普遍的開發(fā)環(huán)境中，long型的數(shù)據(jù)大小小于1011，double型的數(shù)據(jù)精度小于16位），就必須設(shè)計新的數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲，并定義基于新結(jié)構(gòu)的基本運算[1]。在本文中，我們將分析大整數(shù)的存儲和運算的實現(xiàn)。

根據(jù)如何存儲大整數(shù)的方法不同，我們將實現(xiàn)方法分為數(shù)組方式實現(xiàn)和鏈表方式實現(xiàn)兩種。

1 數(shù)組方式實現(xiàn)分析

1）大整數(shù)數(shù)組存儲

在數(shù)制表達(dá)當(dāng)中，進(jìn)制數(shù)（即基數(shù)）是基礎(chǔ)。一個整數(shù)A表達(dá)成 A = (a0a1… an)，其實際表示的是一個以 a0、 …an為系數(shù)的多項式: A =，其中的X表示基數(shù)[2]。所以，存儲一個大整數(shù)，實際上就是存儲這些系數(shù)，而最直觀的就是數(shù)組存儲了。但如果一個數(shù)組元素存儲一個十進(jìn)制系數(shù)，會存在明顯的空間浪費，運算實現(xiàn)過程也會出現(xiàn)循環(huán)次數(shù)過多的問題，效率低。因此要選擇合適的基數(shù)X:分析發(fā)現(xiàn)如果取X=10000是比較合適的，一方面并沒有超出long型數(shù)據(jù)的范圍，另一方面會減少大整數(shù)的實際位數(shù)，提高空間和時間上的效率。同時，十進(jìn)制數(shù)轉(zhuǎn)換為萬進(jìn)制數(shù)不會改變大整數(shù)原有的數(shù)字形式，也就不需要多余的數(shù)字轉(zhuǎn)換運算，只需要把原數(shù)的每四位看成一個整體，依次存入數(shù)組而已。需要注意的是，原整數(shù)低位在右側(cè)，而數(shù)組的低位在左側(cè)，因此為了計算方便，存儲時，新的萬進(jìn)制數(shù)采取逆序存放。按照如上描述，一個大整數(shù)98765432109876543210采取上述方法存儲如下樣子（每一段對應(yīng)一個數(shù)組元素，并與數(shù)組元素先后次序一致，第一個數(shù)即為下標(biāo)0的元素，注意最后一個的位數(shù)可能小于4）:

而為了運算和判斷的方便，我們還須對大整數(shù)進(jìn)行結(jié)構(gòu)封裝，增加記錄“系數(shù)個數(shù)”和“正負(fù)符號”兩個成員。因此可得大整數(shù)結(jié)構(gòu)如下:

2）大整數(shù)加減法

對同正或同負(fù)的兩個大整數(shù)，它們之間的加法運算，和的符號同加數(shù)，和值只需對兩個加數(shù)數(shù)組的對應(yīng)元素相加，并考慮進(jìn)位即可。兩個加數(shù)A和B的系數(shù)個數(shù)（也就是數(shù)組有效元素個數(shù)、或整數(shù)的位數(shù)）的大小關(guān)系存在三種可能，因此在實現(xiàn)中，以較少的系數(shù)有多少個來劃分有較多系數(shù)的加數(shù)，這樣就可以對低位相同長度的部分對應(yīng)相加，對高位多出的部分直接賦值到和數(shù)組。

對異號整數(shù)的加法運算，實際上是減法運算。它的運算過程與同符號加法相類似，也需要對系數(shù)較多的加數(shù)進(jìn)行劃分，低位相同長度的部分相減，高位部分直接賦值。不過在運算之前需要作預(yù)處理:首先要比較兩個數(shù)的大?。ú豢紤]正負(fù)號），把較大的數(shù)作被減數(shù)，經(jīng)過這步處理，也可以確定差值得符號——與較大的數(shù)相同，然后作減法運算。

3）大整數(shù)乘法

首先，我們分析一下自然乘法運算的過程:排豎式依次用乘數(shù)的每一位去乘被乘數(shù)的各位數(shù)字，再加上上一步運算的進(jìn)位，最后累加結(jié)果。

以上過程是非常有規(guī)律的，兩個運算數(shù)A和B也都是逆序存放在數(shù)組中，因此可以利用for語句逐步進(jìn)行:首先定義積數(shù)組result并初始化為0，則自然乘法運算的過程可以對兩個運算數(shù)數(shù)組下標(biāo)進(jìn)行循環(huán)，同時依次相乘和最后累加這兩個步驟可以進(jìn)行合并:

result[i+j] += A[i] * B[j] % 10000; //各位數(shù)字乘積對基數(shù)的模存放在第i+j位

result[i+j+1] += A[i] * B[j] / 10000; //乘積對基數(shù)的商表示需進(jìn)位，并進(jìn)位到高一位

以上所述實現(xiàn)的是乘法的自然算法，不難發(fā)現(xiàn)該算法需頻繁地進(jìn)行模、商和進(jìn)位運算，增加了運算次數(shù)，對這一點我們還可以進(jìn)行如下改進(jìn)。

自然算法過程是依次出現(xiàn)每行的乘積，然后對應(yīng)列相加，從而導(dǎo)致模、商和進(jìn)位運算重復(fù)進(jìn)行。我們改變運算次序，先計算每一列的數(shù)字(各位數(shù)字相乘但不進(jìn)位)，然后再進(jìn)行橫向的運算:在最后才開始從低位向高位逐位進(jìn)行進(jìn)位修正。方法是:模留在本位，而商則進(jìn)位到高一位。

4）大整數(shù)除法

除法運算是最復(fù)雜的，也是效率最低的。根據(jù)除法的一般定義，我們可以借助減法來實現(xiàn):以差值是否小于除數(shù)作為判斷條件進(jìn)行循環(huán)運算，以一個計數(shù)器統(tǒng)計循環(huán)次數(shù)，則計數(shù)器的終值即為商，最終的差值即為余數(shù)。

2 鏈表方式實現(xiàn)分析

1）大整數(shù)鏈?zhǔn)酱鎯?/p>

同前面一樣，取基數(shù)X=10000，將大整數(shù)從低位每4位構(gòu)成一個系數(shù)存入鏈表的每一個結(jié)點。同樣考慮到輸入輸出數(shù)據(jù)時高位在先，而計算時一般從低位開始，因此采用雙向鏈表存儲大整數(shù)。這樣一個大整數(shù)就對應(yīng)了一個鏈表，并給該鏈表設(shè)置一個頭結(jié)點，該結(jié)點的數(shù)據(jù)域表示大整數(shù)的符號及系數(shù)個數(shù):數(shù)據(jù)域的符號與大整數(shù)符號一致，絕對值則表示系數(shù)的多少。因此可得大整數(shù)的結(jié)點結(jié)構(gòu)如下:

2）鏈表存儲的基本運算算法和前述的方法差別不大，將遍歷數(shù)組換成遍歷鏈表即可。

3 輸入輸出處理

大整數(shù)的輸入可以從鍵盤輸入，也可以從文件讀入。如果從鍵盤輸入，則按照字符輸入，首先讀取首字符正負(fù)號，一般正號不輸入，首字符如果是負(fù)號，則修改數(shù)據(jù)結(jié)構(gòu)中相應(yīng)的字段:數(shù)組方式中的sign成員或鏈表方式中的頭結(jié)點。后續(xù)的數(shù)字連續(xù)輸入構(gòu)成一個字符串，將該字符串從后往前遍歷，每四位一組存入數(shù)組元素或結(jié)點數(shù)據(jù)域。

如果從文件讀取大整數(shù)，處理相對簡單，可以使用相關(guān)庫函數(shù)分段截取，存入數(shù)組元素或結(jié)點數(shù)據(jù)域[3]。

對數(shù)據(jù)的輸出，由于選用的基數(shù)的關(guān)系，各數(shù)字形式未發(fā)生變化，因此只需逆序遍歷數(shù)組或鏈表，依次輸出數(shù)組元素或鏈表的數(shù)據(jù)域。

4 兩種存儲方式的比較

從空間使用來看，鏈表方式除了存儲數(shù)據(jù)本身，還包含大量的指針域，同時由于數(shù)據(jù)離散存儲，在實現(xiàn)中勢必頻繁進(jìn)行堆操作，也會大量增加空間開銷。而數(shù)組方式，空間利用率較高，但運算過程容易超界，需額外定義一個擴展函數(shù)，以便隨時進(jìn)行空間追加。

從時間效率上看，數(shù)組方式要比鏈?zhǔn)椒绞剿钑r間要少。這是由于數(shù)組存儲的數(shù)據(jù)是連續(xù)存放的，因此運算時可以根據(jù)位數(shù)，也就是數(shù)組下標(biāo)進(jìn)行直接訪問；而鏈?zhǔn)降臄?shù)據(jù)是離散的，它必須從頭結(jié)點開始，依次查詢直到找到，從而造成耗時增加[4]。

5 結(jié)論

大整數(shù)，尤其是超大整數(shù)（大于263 的數(shù)）的應(yīng)用范圍很多，由于受字長所限，我們需設(shè)計新的數(shù)據(jù)結(jié)構(gòu)來存儲，并實現(xiàn)基本四則運算，而其他運算，如冪運算則可以轉(zhuǎn)化為基本的四則運算來實現(xiàn)，從而在信息安全、數(shù)學(xué)驗證、微觀模擬等領(lǐng)域展開廣泛應(yīng)用。

[1] 譚浩強.C語言程序設(shè)計[M].北京:清華大學(xué)出版社，1999:41-43.

[2] 張力，張引兵.一種新的大整數(shù)乘法算法[J].計算機安全，2011，1:11-13.

[3] 李文化.大整數(shù)精確運算系統(tǒng)研究與開發(fā).重慶大學(xué)，2005，8.

[4] 凌晨，買磊.基于兩種不同存儲方式的大整數(shù)運算及性能比較[J].安慶師范學(xué)院學(xué)報，2003，9(1):86-88.