大整數基本運算的實現分析

柴 君

天津電子信息職業技術學院，天津 300350

0 引言

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

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

根據如何存儲大整數的方法不同，我們將實現方法分為數組方式實現和鏈表方式實現兩種。

1 數組方式實現分析

1）大整數數組存儲

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

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

2）大整數加減法

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

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

3）大整數乘法

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

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

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

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

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

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

4）大整數除法

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

2 鏈表方式實現分析

1）大整數鏈式存儲

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

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

3 輸入輸出處理

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

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

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

4 兩種存儲方式的比較

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

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

5 結論

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

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

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

[3] 李文化.大整數精確運算系統研究與開發.重慶大學，2005，8.

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