高精度加法的輸入及處理方式淺析

趙心龍（山東省廣饒縣第一中學）

?

高精度加法的輸入及處理方式淺析

趙心龍
（山東省廣饒縣第一中學）

摘要：利用計算機進行數值運算，經常會遇到數值太大的情況，有時又會遇到對運算的精度要求特別高的情況。針對這些情況，都要用“高精度運算”來解決，下面以加法為例簡要分析高精度運算的輸入及處理方式。

關鍵詞：高精度；數組；字符串

利用計算機進行數值運算，經常會遇到數值太大，超出Longint、int64等系統標準數據類型的有效范圍；有時又會遇到對運算的精度要求特別高的情況，如計算圓周率π，要求精確到小數點后100位，此時real、double等數據類型也無能為力了。針對這些情況，就需要用“高精度運算”來解決。

高精度數據的讀入可以采用兩種方法，一是一位一位讀入并存儲到數組中；二是采用字符串方式讀入，再逐位處理成數字存儲在數組中。在實際使用時，按大家習慣可以選擇不同的處理方式。高精度運算一般都是采用模擬的方法解決，所以輸入時一定要注意按位對齊。

一、采用數組方式讀入，按數組進行運算

定義存儲數組：var p：array［1..n］of integer；

代碼一：read（ch）；

k：=0；

while ch in［‘0’..‘9’］do//讀入數組

begin

inc（k）；

p［k］：=ord（ch）-48；

read（ch）；

end；

read（ch）將數據一位一位讀入。k初值為零，且循環過程中遞增，p［1］至p［k］依次存儲數據的高位至低位。

代碼二：for i：=k downto 1 do//處理數組，使數據按位右對齊

begin

p［n+i-k］：=p［i］；

p［i］：=0；

end；

p［n+i-k］：=p［i］將整個數組向后平移，最后一位移至p［n］，第一位移至p［n+1-k］，使參與運算的數據按位右對齊。

代碼二在代碼一的基礎上，經過處理后，兩個高精度數低位對齊，符合我們做加法、減法、乘法的運算習慣。

二、采用字符串方式讀入，轉換成數組運算

定義字符串：var sa，sb：string；數據類型string定義的字符串長度為0-255，如果輸入更長的字符串，可以將字符串定義為無限字符串ansistring。

用字符串方式讀入兩個高精度數，readln（sa）；readln（sb）；

計算出每個字符串的長度，la：=length（sa）；lb：=length（sb）；

代碼三：for i：=1 to la do a［i］：=ord（sa［la+1-i］）-48；

for i：=1 to lb do b［i］：=ord（sb［lb+1-i］）-48；

字符‘0’的ASSCⅡ碼是48，ord（ ）函數的作用是將字符轉換成數值，例如輸入的字符‘8’，通過ord（8）-48可以將字符‘8’轉換成與之等價的數值，即字符‘8’轉換成數字8。通過下標的變化a［i］：=ord（sa［la+1-i］）-48，將輸入的字符串‘12345’轉換成數組a，每一位數值存儲順序恰與數組a的下標相反，其中a［1］=5，a［2］=4，a［3］=3，a［4］=2，［5］=1。

以上過程是把兩個高精度數逐位處理并轉存到a、b兩個數組中，數組下標從1開始存儲數的低位。這種讀入的方法利用了字符串的性質，符合人們讀數的習慣，但計算時需要將字符串轉換成數組。a［i］：=ord（sa［la+1-i］）-48中sa的下標可以根據自己的習慣靈活處理。

三、采用字符串方式讀入，直接進行運算

代碼四：

while length（sa）＞length（sb）do sb：=‘0’+sb；

while length（sb）＞length（sa）do sa：=‘0’+sa；

比較讀入的兩個字符串長度，通過在字符串前加‘0’的方式將兩個字符串長度補齊，其原理是在數的高位添加0而不影響數的大小。在運算處理方面，我們可以通過字符串的下標如sa［i］訪問字符串中的單個字符，然后將字符轉換成數值進行運算。

高精度運算的首要問題是讀入方式和存儲方式的轉換，方式一時間復雜度O（n）；方式二時間復雜度O（length（s）），如果兩個字符串的長度差大，此方式優于方式一；方式三時間復雜度O（|length （sa）-length（sb）|），如果兩個字符串的長度差小，此方式優于方式一。雖然方式二、三在某些情形下優于方式一，但與人的邏輯習慣不符，所以這幾種方法可以靈活運用。

參考文獻：

［1］吳再陵.全國青少年信息學奧林匹克聯賽培訓教材［M］.南京大學出版社，2006.

［2］狄光智，趙同林.數組實現高精度計算的方法研究［J］.電腦編程技巧與維護，2009（10）.

·編輯姚曉媛