第二章 高精度計算

1、高精度運算所謂的高精度運算是指參與運算的數(shù)(加數(shù)減數(shù)因子……）范圍大大超出了標(biāo)準(zhǔn)數(shù)據(jù)類型（整型，實型）能表示的范圍的運算。例如，求兩個200位的數(shù)的和。這時，就要用到高精度算法了。在這里，我們先討論高精度加法。高精度運算主要解決以下三個問題：基本方法1、加數(shù)、減數(shù)、運算結(jié)果的輸入和存儲運算因子超出了整型、實型能表示的范圍，肯定不能直接用一個數(shù)的形式來表示。在Pal中，能表示多個數(shù)的數(shù)據(jù)類型有兩種：數(shù)組和字符串。（1）數(shù)組：每個數(shù)組元素存

2、儲1位（在優(yōu)化時，這里是一個重點?。?，有多少位就需要多少個數(shù)組元素；用數(shù)組表示數(shù)的優(yōu)點：每一位都是數(shù)的形式，可以直接加減；運算時非常方便用數(shù)組表示數(shù)的缺點：數(shù)組不能直接輸入；輸入時每兩位數(shù)之間必須有分隔符，不符合數(shù)值的輸入習(xí)慣；（2）字符串：字符串的最大長度是255，可以表示255位。用字符串表示數(shù)的優(yōu)點：能直接輸入輸出，輸入時，每兩位數(shù)之間不必分隔符，符合數(shù)值的輸入習(xí)慣；用字符串表示數(shù)的缺點：字符串中的每一位是一個字符，不能直接進(jìn)行運

3、算，必須先將它轉(zhuǎn)化為數(shù)值再進(jìn)行運算；運算時非常不方便；（3）因此，綜合以上所述，對上面兩種數(shù)據(jù)結(jié)構(gòu)取長補(bǔ)短：用字符串讀入數(shù)據(jù)，用數(shù)組存儲數(shù)據(jù)：vars1s2:stringabc:array[1..260]ofintegerilk1k2:integerbeginwrite(inputs1:)readln(s1)write(inputs2:)readln(s2)————讀入兩個數(shù)s1，s2，都是字符串類型l:=length(s1)求出s1的

4、長度，也即s1的位數(shù)；有關(guān)字符串的知識。k1:=260fi:=ldownto1dobegina[k1]:=d(s1[i])48將字符轉(zhuǎn)成數(shù)值k1:=k11endk1:=k11————以上將s1中的字符一位一位地轉(zhuǎn)成數(shù)值并存在數(shù)組a中；低位在后（從第260位開始），高位在前（每存完一位，k1減1）對s2的轉(zhuǎn)化過程和上面一模一樣。2、運算過程在往下看之前，大家先列豎式計算3586。注意的問題：k2:=k21ifk1k2thenk:=k2el

5、sek:=k1y:=0fi:=260downtokdobeginx:=a[i]b[i]yc[i]:=xmod10y:=xdiv10endify0thenbegink:=k1c[k]:=yendfi:=kto260dowrite(c[i])writelnend.優(yōu)化：以上的方法的有明顯的缺點：（1）浪費空間：一個整型變量（32768~32767）只存放一位（0~9）；（2）浪費時間：一次加減只處理一位；針對以上問題，我們做如下優(yōu)化：一個數(shù)

6、組元素存放四位數(shù)；（integer的最大范圍是32767，5位的話可能導(dǎo)致出界）。具體方法：l:=length(s1)k1:=260repeat————有關(guān)字符串的知識s:=copy(s1l34)val(sa[k1]code)k1:=k11s1:=copy(s11l4)l:=l4untill=0k1:=k11而因為這個改進(jìn)，算法要相應(yīng)改變：（1）運算時：不再逢十進(jìn)位，而是逢萬進(jìn)位（mod10000div10000)（2）輸出時：最高位直