FreeBASIC高精度計算講稿

1、高精度計算高精度計算高精度計算的由來與含義在FB中，整型/長長整型數(shù)的長度只有4字節(jié)/8字節(jié)。整型的取值范圍分別為-2147483648 2147483647。Longint數(shù)的長度為19位。如果需要獲得超過這個精度的運算結果（如大整數(shù)相加、相乘、實數(shù)運算要求有多位小數(shù)等），只有靠程序來實現(xiàn)了也稱為“大整數(shù)運算”；在通過程序獲得更高的精度的做法中，通常是利用數(shù)組，把每一位數(shù)字存放在一個元素中，然后，模仿筆算的方式，一位一位地計算，這就是計算機的高精度計算* 數(shù)組存儲的優(yōu)化：優(yōu)化空間、計算量；高精度計算的主要步驟：高精度計算的主要步驟：高精度計算要分三個方面來處理：數(shù)據(jù)的輸入與存儲，估計結果的位

2、數(shù)（How？），定義存儲數(shù)組的大??；運算：加法的進位、減法的借位，乘法的積，除法的商和余數(shù)的處理；1)結果的輸出。原始數(shù)據(jù)的輸入與存儲原始數(shù)據(jù)的輸入與存儲數(shù)字分離，存入數(shù)組數(shù)字分離，存入數(shù)組輸入一個正整數(shù)(以回車結束)，把各位數(shù)字從此數(shù)中分離出來，通常用 MOD 和整除兩個操作來完成，每位數(shù)字都存入數(shù)組的一個元素中。問題：若輸入的值超過了整型的范圍？數(shù)字一個一個輸入，存入數(shù)組一個正整數(shù)，把它的數(shù)字從最高位開始，一個一個輸入，直至最后一個數(shù)字，再輸入一個任意負數(shù)，表示輸入結束。每輸入一個數(shù)字，就存入數(shù)組的一個元素之中。具體操作如下：輸入一個數(shù)字，如為負數(shù)，就結束輸入；判斷此數(shù)字是否合法，合法就存

3、入數(shù)組，不合法就顯示出錯的停息，結束；1)重復(1)、(2)操作。例如，輸入一個四位數(shù)1234后，在數(shù)組a()中就存放了各位數(shù)字。 數(shù)組a()的各元素： a(1) a(2) a(3) a(4) 1 2 3 4這樣，各數(shù)字的位權與下標的序號相反，因而，輸入時無法預先確定數(shù)字的位數(shù)，就只好將數(shù)組定義得大一點，如 DIM A(100)或者：視題目中數(shù)據(jù)范圍而定；能否正序存放？數(shù)字字符串分離轉成數(shù)存入數(shù)組輸入一個數(shù)字字符串，以回車結束，計算其長度，定義數(shù)組；用MID(A_STR,I,1)依次一一分離出字符；判斷此字符是否是數(shù)字字符，是就轉為數(shù)字存入數(shù)組，否就顯示出錯信息，結束；如沒有分離完就重復(2)

4、、(3)的操作，若已分離完則結束。數(shù)字字符串分離轉成數(shù)存入數(shù)組（續(xù)）例如，輸入一個字符串“1234”后，在數(shù)組a()中就存放了各位數(shù)字： a(1) a(2) a(3) a(4) 1 2 3 4 在這樣的存放方式下，數(shù)字的位權與下標序號反向存入數(shù)組反序存儲便于后面的計算； 初賽中常見“正序存儲”。數(shù)字以字符形式一個一個輸入轉成數(shù)存入數(shù)組把一個正整數(shù)的各位數(shù)字以字符的形式，從最高位開始，一個一個輸入，最后輸入一個“$”符號表示輸入結束數(shù)字字符轉為數(shù)字，分別存入數(shù)組，這種方法類似方法2，只是加上了字符轉為數(shù)字的內容四種方法的比較第一種方法輸入簡單方便，但精度有限第二、四種方法數(shù)據(jù)輸入太繁，但精度不限

5、；第三種數(shù)據(jù)輸入簡單方便，且精度比第一種方式高得多，能應付較高的需要，比較實用。下面的例子大多采用第三種方法。四種基本的高精度計算高精度加法高精度減法高精度乘法高精度除法高精度加法高精度加法 高精度加法運算的算法，需要從輸入、處理和輸出這三部分來分析數(shù)據(jù)的輸入與存儲，估計結果的位數(shù)，定義存儲數(shù)組的大小設參與加法運算的兩個數(shù)串為 a_str 和 b_str：輸入 a_str 與 b_str，計算兩者的長度 La = LEN(a_str) : Lb = LEN(b_str)比較 La 與 Lb 的大小，如 Lb 大，要交換 a_str 和b_str (同時交換La和Lb)，然后定義數(shù)組： DIM

6、as integer a(La+1), b(La+1)DIM as integer a(La+1), b(La+1)1)兩數(shù)相加，其和存放在 a() 數(shù)組中，不再開辟新的存儲單元；數(shù)據(jù)的輸入與存儲，估計結果的位數(shù)，定義存儲數(shù)組的大小分離 a_str 和 b_str，分別存入數(shù)組 a()和 b() 。例如： a_str = “12345678” b_str = “123456”加法運算是從個位開始的，分離時下標序號與位權一致，這樣運算起來就比較方便了 Why ? 此時，a(1)a(9)的值分別為8、7、6、5、4、3、2、1、0，b(1)b(9)的值分別為6、5、4、3、2、1、0、0、0。兩數(shù)

7、從低位到高位，各位數(shù)字分別相加若某單元中的數(shù)值10的話，就要發(fā)生進位，即從本位中減去10，并將下一個單元的數(shù)值加1，具體操作如下： a(i)=a(i)+b(i) IF a(i)=10 THEN a(i) = a(i)-10 a(i+1) = a(i+1) + 1 END IF 這就是加法進位的算法，可以簡化為： x = a(i) + b(i) a(i+1) = a(i+1) + x 10 a(i) = x mod 10 結果的輸出注意：和的最后一位不一定進位，所以要判斷最高位的值。如果是0，則這一位就不輸出；1)因數(shù)據(jù)存放時，位權與下標序號是一致的，所以輸出時用遞減循環(huán)。高精度減法高精度減法運

8、算的算法，也需要從輸入、處理和輸出三部分來分析：數(shù)據(jù)的輸入與存儲，定義數(shù)組的大小兩數(shù)從低位到高位，各位數(shù)字分別相減數(shù)據(jù)的輸入與存儲，定義數(shù)組的大小這一部分與加法不同的是：比較兩個數(shù)的大小，如減數(shù)大，要用一個符號變量記下“-”，兩數(shù)交換后，仍作大數(shù)減小數(shù)處理，只是在輸出時，在前面加上“-”號；比較的方法，與加法也有區(qū)別，如只比較La與Lb，當然長的數(shù)大，但當La與Lb相等時，就無法處理了，這時，還要加上a_str與b_str的比較。以大數(shù)的大小來定義數(shù)組： DIM AS INTEGER A(LA), B(LA) 兩數(shù)的差存儲在A()數(shù)組中。兩數(shù)從低位到高位，各位數(shù)字分別相減如某單元中的數(shù)值a(i

9、)b(i)時，就要借位，從下一個單元的數(shù)值中借1，本單元的數(shù)值加上10，然后再減，具體操作如下： IF A(I) B(I) THEN A(I+1) = A(I+1) - 1 A(I) = A(I) + 10 END IF A(I) = A(I) B(I)也可以先減，再判斷是否需要借位： A(I) = A(I) B(I) IF A(I)1 N = N-1 WEND高精度乘法高精度乘法的算法，仍以輸入、處理和輸出三部分來分析：數(shù)據(jù)的輸入與存儲，定義存儲數(shù)組的大小，這一部分與加法的不同點是： 增加一個存放乘積的數(shù)組c()，定義c(La+Lb) 問題：能否就把相乘的結果存放到A()中？1)兩數(shù)相乘兩數(shù)

10、相乘先從乘數(shù)的個位，分別與被乘數(shù)的由低位到高位的各位數(shù)字一一相乘；再以乘數(shù)的十位，分別與被乘數(shù)的由低位到高位的各位數(shù)字一一相乘； 直到乘數(shù)的最高位，分別與被乘數(shù)的由低位到高位的各位數(shù)字一一相乘。因此，乘法要用兩重循環(huán)來實現(xiàn)，而循環(huán)體中的每次操作都要：乘法進位：x=a(i) * b(j)，x是 a( ) 數(shù)組中 i 位數(shù)與 b( )數(shù)組中的 j 位數(shù)的乘積： y = x 10 y是要進位的數(shù) z = z mod 10 z是本位的數(shù) 乘積的位數(shù)是 w = i+j-1，在后面的加法進位時，再把y與z存入乘積數(shù)組c()中加法進位：把 z 加到乘積數(shù)組中c(w)=c(w)+z，這時的c(w)如果超過了1

11、0，還要進位。 把 y 與 c(w) 中的進位加到乘積數(shù)組中 c(w+1) = c(w+1) + y + c(w) 10 c(w)中去掉進位后的數(shù)值是 c(w) = c(w) MOD 10 弄清楚了乘法進位與加法進位，可以把它們合寫成： X = A(I) * B(J) W = I + J 1 C(W) = C(W) + X MOD 10 C(W+1) = C(W+1) + X 10 + C(W) 10 C(W) = C(W) MOD 10結果的輸出與減法相同。想一想：能否編寫一個高精度求2n、n!的程序？高精度除法例8 被除數(shù)與除數(shù)是整型數(shù)，商是高精度的除法(指定保留e位小數(shù))。算法分析算法分

12、析設a、b是兩個系統(tǒng)允許的整型數(shù)，a/b的值有兩種情況：a能被b整除，沒有余數(shù)；a不能被b整除，有余數(shù)?？梢钥闯?，在做除法運算時，除數(shù)(b)是始終不變的，商數(shù)(d)和余數(shù)(a)是變的。下一次的被除數(shù)是“余數(shù)*10”，也是跟著變的。這三個變量之間的關系是： a = a * 10 : d=a b PRINT USING “#” ; d; d是一位商(小數(shù))，一定要及時輸出 a = a MOD b 把以上的三個語句放在一個循環(huán)里，一個除法運算就形成了。確定商的精度取幾位小數(shù)的問題，可以輸入一個正整數(shù)e來確定商的精度。例例9 被除數(shù)與除數(shù)是整型數(shù)，商是高精度的除法(指定保留e位小數(shù))。如是循環(huán)小數(shù)輸出

13、循環(huán)節(jié)，循環(huán)節(jié)用 表示。算法分析 在除法運算中，如不能整除，就有三種情況：有限小數(shù)，最后除盡；循環(huán)小數(shù)，由指定的精度，輸出e位小數(shù)；1)循環(huán)小數(shù)，輸出循環(huán)節(jié)。上例解決了前兩種情況，現(xiàn)在來討論如何處理循環(huán)小數(shù)的情況。判斷循環(huán)小數(shù)，只要看余數(shù)是否重復出現(xiàn)。若余數(shù)重復出現(xiàn)，所得商就會重復出現(xiàn)，這就產(chǎn)生了循環(huán)小數(shù)處理的方法：可把每次出現(xiàn)的不同余數(shù)用數(shù)組記錄下來，若以后的操作中產(chǎn)生了新的余數(shù)，與數(shù)組中的余數(shù)相同，就證明出現(xiàn)了循環(huán)。除法運算終止。這時，只要把循環(huán)的部分輸出即可。建立兩個數(shù)組：用A( )數(shù)組來存放余數(shù)，用D( )數(shù)組來存放商數(shù)。數(shù)組的大小由e確定在運算的過程中，可能出現(xiàn)三種情況：有限小數(shù)，最

14、后除盡，就中斷循環(huán)，記下循環(huán)變量當時的值，用以判斷不輸出循環(huán)節(jié)；循環(huán)小數(shù)，由指定的精度終止，輸出e位小數(shù)；1)循環(huán)小數(shù)，在e位小數(shù)前出現(xiàn)循環(huán)，記下循環(huán)變量當時的值，用以判斷輸出循環(huán)節(jié)。例例10 被除數(shù)用數(shù)組存放，除數(shù)是個整型數(shù)，商是高精度的除法，如除不盡留余數(shù)。 高精度數(shù)除以普通整數(shù) 算法分析算法分析數(shù)據(jù)的輸入與存儲，定義存儲數(shù)組的大小，要定義存儲被除數(shù)被除數(shù)和商數(shù)商數(shù)兩個數(shù)組兩個數(shù)組數(shù)據(jù)處理算法分析：算法分析：除法運算是從最高位開始的，所以分離被除數(shù)時，數(shù)據(jù)的位權與下標序號正好相反。 正序存放正序存放 用一個計數(shù)循環(huán)，從 1 到La： 一位一位取出被除數(shù)；一位一位取出被除數(shù)； 在除法運算中，

15、每次都要把上一次的余數(shù)在除法運算中，每次都要把上一次的余數(shù)* *1010，再加上取出的本位被除數(shù)再加上取出的本位被除數(shù) ( ( 與與 例例9 9 不同不同 ) )，臨時組成被除數(shù)。臨時組成被除數(shù)。具體的算法是： Y = Y * 10 + A(K) A(K)：被除數(shù) D(K) = Y B D(K)：商 Y = Y MOD B 余數(shù)循環(huán)結束時，如除不盡，余數(shù)保存在 y 中。第一次做除法運算前，先設 Y = 0。結果輸出有時，商數(shù)組前面有許多單元中存的是0。前面的無用的0不輸出： K = 1 DO WHILE A(K) = 0 K = K + 1 LOOPdim as string aainput a=,aadim as integer b, a(100), d(100)input b=, b