大整數(shù)基本運算的實現(xiàn)分析

柴 君

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

0 引言

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

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

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

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

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

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

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

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

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

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

3）大整數(shù)乘法

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

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

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

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

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

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

4）大整數(shù)除法

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

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

1）大整數(shù)鏈式存儲

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

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

3 輸入輸出處理

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

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

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

4 兩種存儲方式的比較

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

從時間效率上看，數(shù)組方式要比鏈式方式所需時間要少。這是由于數(shù)組存儲的數(shù)據(jù)是連續(xù)存放的，因此運算時可以根據(jù)位數(shù)，也就是數(shù)組下標進行直接訪問；而鏈式的數(shù)據(jù)是離散的，它必須從頭結點開始，依次查詢直到找到，從而造成耗時增加[4]。

5 結論

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

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

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

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

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