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

趙心龍（山東省廣饒縣第一中學(xué)）

?

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

趙心龍
（山東省廣饒縣第一中學(xué)）

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

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

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

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

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

定義存儲數(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］，使參與運(yùn)算的數(shù)據(jù)按位右對齊。

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

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

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

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

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

三、采用字符串方式讀入，直接進(jìn)行運(yùn)算

代碼四：

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

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

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

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

參考文獻(xiàn)：

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

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

·編輯姚曉媛