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

趙心龍

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

關鍵詞：高精度；數(shù)組；字符串

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

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

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

定義存儲數(shù)組：var p：array[1..n] of integer；

代碼一：read（ch）；

k：=0；

while ch in[‘0..‘9] do //讀入數(shù)組

begin

inc（k）；

p[k]：=ord（ch）-48；

read（ch）；

end；

read（ch）將數(shù)據(jù)一位一位讀入。k初值為零，且循環(huán)過程中遞增，p[1]至p[k]依次存儲數(shù)據(jù)的高位至低位。

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

begin

p[n+i-k]：=p[i]；

p[i]：=0；

end；

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

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

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

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

用字符串方式讀入兩個高精度數(shù)，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（ ）函數(shù)的作用是將字符轉換成數(shù)值，例如輸入的字符‘8，通過ord（8）-48可以將字符‘8轉換成與之等價的數(shù)值，即字符‘8轉換成數(shù)字8。通過下標的變化a[i]：=ord（sa[la+1-i]）-48，將輸入的字符串‘12345轉換成數(shù)組a，每一位數(shù)值存儲順序恰與數(shù)組a的下標相反，其中a[1]=5，a[2]=4，a[3]=3，a[4]=2，[5]=1。

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

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

代碼四：

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

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

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

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

參考文獻：

[1]吳再陵.全國青少年信息學奧林匹克聯(lián)賽培訓教材[M].南京大學出版社，2006.

[2] 狄光智，趙同林.數(shù)組實現(xiàn)高精度計算的方法研究[J].電腦編程技巧與維護，2009（10）.

編輯 姚曉媛