第二章 高精度計(jì)算

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

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

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

4、長(zhǎng)度，也即s1的位數(shù)；有關(guān)字符串的知識(shí)。k1:=260fi:=ldownto1dobegina[k1]:=d(s1[i])48將字符轉(zhuǎn)成數(shù)值k1:=k11endk1:=k11————以上將s1中的字符一位一位地轉(zhuǎn)成數(shù)值并存在數(shù)組a中；低位在后（從第260位開始），高位在前（每存完一位，k1減1）對(duì)s2的轉(zhuǎn)化過程和上面一模一樣。2、運(yùn)算過程在往下看之前，大家先列豎式計(jì)算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)化：以上的方法的有明顯的缺點(diǎn)：（1）浪費(fèi)空間：一個(gè)整型變量（32768~32767）只存放一位（0~9）；（2）浪費(fèi)時(shí)間：一次加減只處理一位；針對(duì)以上問題，我們做如下優(yōu)化：一個(gè)數(shù)

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