2015課件高精度計算

1、高精度計算所謂的高精度運算,是指參與運算的數(加數,減數,因子）范圍大大超出了標準數據類型（整型，實型）能表示的范圍的運算。例如，求兩個200位的數的和。大整數加法問題描述求兩個不超過200 位的非負整數的和。輸入數據：有兩行，每行是一個不超過200 位的非負整數，沒有多余的前導0。輸出要求：一行，即相加后的結果。結果里不能有多余的前導0，即如果結果是342，那么就不能輸出為0342。輸入樣例 22 33輸出樣例 55 首先要解決的就是存儲200 位整數的問題。顯然，任何C/C+固有類型的變量都無法保存它。最直觀的想法是可以用一個字符串來保存它。字符串本質上就是一個字符數組，因此為了編程更方便

2、，我們也可以用數組unsigned an200來保存一個200 位的整數，讓an0存放個位數，an1存放十位數，an2存放百位數 那么如何實現(xiàn)兩個大整數相加呢？方法很簡單，就是模擬小學生列豎式做加法，從個位開始逐位相加，超過或達到10 則進位。也就是說，用unsigned an1201保存第一個數，用unsigned an2200表示第二個數，然后逐位相加，相加的結果直接存放在an1 中。要注意處理進位。另外，an1 數組長度定為201，是因為兩個200 位整數相加，結果可能會有201 位。 實際編程時，不一定要費心思去把數組大小定得正好合適，稍微開大點也無所謂，以免不小心沒有算準這個“正好合

3、適”的數值，而導致數組小了，產生越界錯誤。3、解題思路4、參考程序#include #include #define MAX_LEN 200int an1MAX_LEN+10;int an2MAX_LEN+10;char szLine1MAX_LEN+10;char szLine2MAX_LEN+10;int main(void) scanf(%s, szLine1); scanf(%s, szLine2); int i, j; memset( an1, 0, sizeof(an1); memset( an2, 0, sizeof(an2);6/334、參考程序 int nLen1 = str

4、len( szLine1); for( j = 0, i = nLen1 - 1;i = 0 ; i -) an1j+ = szLine1i - 0; int nLen2 = strlen(szLine2); for( j = 0, i = nLen2 - 1;i = 0 ; i -) an2j+ = szLine2i - 0; for( i = 0;i = 10 ) /看是否要進位 an1i -= 10; an1i+1 +; /進位 for( i = MAX_LEN; (i = 0) & (an1i = 0); i - ) ; if(i=0) for( ; i = 0; i-) printf

5、(%d, an1i); else printf(0); return 0;4、參考程序bool bStartOutput = false; /此變量用于跳過多余的0 for( i = MAX_LEN; i = 0; i - ) if( bStartOutput) printf(“%d”, an1i); else if( an1i ) printf(%d, an1i);bStartOutput = true; /-return 0;思考：這段代碼有問題嗎？/另一種方法 for( i = MAX_LEN; (i = 0) & (an1i = 0); i - ) ; if(i=0) for( ; i

6、 = 0; i-) printf(%d, an1i); else printf(0); return 0;是否可以對上述程序進一步優(yōu)化？ 思考一個數組存儲一位的缺點：（1）浪費空間：一個int型空間只存放一位（2）浪費時間：一次加減只處理一位針對以上問題，做如下優(yōu)化：一個數組元素存放k位數注意： 運算時：不再逢十進位，而是逢10k進位根據操作（加減法，乘法）決定結果數組的類型，否則會出現(xiàn)越界的情況輸出時對非最高位的補零處理 第一個作業(yè)！注意的問題：（1）運算順序：兩個數靠右對齊；從低位向高位運算；先計算低位再計算高位；（2）運算規(guī)則：同一位的兩個數相加再加上從低位來的進位，成為該位的和；這個和

7、去掉向高位的進位就成為該位的值，可借助取模、整除運算完成；（3）最后一位的進位：如果完成兩個數的相加后，進位位值不為0，則應添加一位；（4）如果兩個加數位數不一樣多，則按位數多的一個進行計算；大整數加法算法流程:(1).讀入被減數S1，S2（字符串）；(2).置符號位：判斷被減數是否大于減數：大則將符號位置為空；小則將符號位置為“- ”，交換減數與被減數；(3).被減數與減數處理成數值，放在數組中；(4).運算：A、取數；B、判斷是否需要借位；C、減，將運算結果放到差數組相應位中；D、判斷是否運算完成：是，轉5；不是，轉A；(5).打印結果：符號位，第1位，循環(huán)處理第2到最后一位；大整數減法思

8、考：大整數減法如何實現(xiàn)？第二個作業(yè)！大整數乘法問題描述求兩個不超過200 位的非負整數的積。輸入數據有兩行，每行是一個不超過200 位的非負整數，沒有多余的前導0。輸出要求一行，即相乘后的結果。結果里不能有多余的前導0，即如果結果是342，那么就不能輸出為0342。輸入樣例 12345678900 98765432100 輸出樣例 0000 在程序中，用unsigned an1200和unsigned an2200分別存放兩個乘數，用aResult400來存放積。計算的中間結果也都存在aResult中。aResult長度取400是因為兩個200 位的數相乘，積最多會有400 位。an10, a

9、n20, aResult0都表示個位。計算的過程基本上和小學生列豎式做乘法相同。為編程方便，并不急于處理進位，而將進位問題留待最后統(tǒng)一處理?，F(xiàn)以 83549 為例來說明程序的計算過程。解題思路現(xiàn)以 83549 為例來說明程序的計算過程。先算8359。59 得到45 個1，39 得到27 個10，89 得到72 個100。由于不急于處理進位，所以8359 算完后，結果如下：解題思路接下來算45。此處45 的結果代表20 個10，因此要 c1+=20，變?yōu)椋涸傧聛硭?3。此處43 的結果代表12 個100，因此要 c2+= 12，變?yōu)椋航忸}思路最后算 48。此處48 的結果代表 32 個1000，

10、因此要 c3+= 32，變?yōu)椋撼朔ㄟ^程完畢。接下來從 c0開始向高位逐位處理進位問題。c0留下5，把4 加到c1上，c1變?yōu)?1 后，應留下1，把5 加到c2上最終使得c 里的每個元素都是1 位數，結果就算出來了：規(guī)律：一個數的第i 位和另一個數的第j 位相乘所得的數，一定是要累加到結果的第i+j 位上。這里i, j 都是從右往左，從0 開始數。4、參考程序#include #include #define MAX_LEN 200int main(void) int i, j; int len1,len2; int aMAX_LEN+10,bMAX_LEN+10,cMAX_LEN*2+10;

11、char str1MAX_LEN+10,str2MAX_LEN+10; for(i=0;iMAX_LEN+10;i+) ai=bi=0; for(i=0;i=0; i-)/把數字倒過來 aj+=str1i-0; len2=strlen(str2); for(j=0,i=len2-1; i=0; i-)/倒轉第二個整數 bj+=str2i-0;4、參考程序 for(i=0; ilen2; i+)/用第二個數乘以第一個數,每次一位 for(j=0; jlen1; j+) ci+j+= bi*aj; /先乘起來,后面統(tǒng)一進位 for(i=0; i=10) ci+1+=ci/10; ci%=10; f

12、or(i=MAX_LEN*2; (ci=0)&(i=0); i-);/跳過高位的0 if(i=0) for(;i=0;i-) printf(%d, ci); else printf(0); return 0;可以用減法代替除法運算：不斷比較A1.n與B1.n的大小，如果A1.n=B1.n則商C1.n+1C1.n，然后就是一個減法過程：A1.n-B1.nA1.n。由于簡單的減法速度太慢，因此必須進行優(yōu)化。 設置一個位置值J，當A1.nB1.n時，B1.n左移B0.n，j:=j+1，即令B1.n增大10倍。這樣就減少了減法的次數。當j0且A1.nB1.n時，B0.n右移。大整數除法大整數除法問題描

13、述 求兩個大的正整數相除的商 輸入數據 第1 行是測試數據的組數n，每組測試數據占2 行，第1 行是被除數，第2 行是除數。每組測試數據之間有一個空行，每行數據不超過100 個字符 輸出要求 n 行，每組測試數據有一行輸出是相應的整除商問題描述輸入樣例3 6 7894 0000000000000000000000010000000000 84354353451輸出樣例0 0000000000000 8435435345 基本的思想是反復做減法，看看從被除數里最多能減去多少個除數，商就是多少。一個一個減顯然太慢，如何減得更快一些呢？以7546 除以23 為例來看一下：開始商為0。先減去23 的1

14、00 倍，就是2300，發(fā)現(xiàn)夠減3 次，余下646。于是商的值就增加300。然后用646 減去230，發(fā)現(xiàn)夠減2 次，余下186，于是商的值增加20。最后用186 減去23，夠減8 次，因此最終商就是328。 所以本題的核心是要寫一個大整數的減法函數，然后反復調用該函數進行減法操作。 計算除數的10 倍、100 倍的時候，不用做乘法，直接在除數后面補0 即可。解題思路參考程序#include #include #define MAX_LEN 200char szLine1MAX_LEN + 10;char szLine2MAX_LEN + 10;int an1MAX_LEN + 10; /被除

15、數, an10對應于個位int an2MAX_LEN + 10; /除數, an20對應于個位int aResultMAX_LEN + 10; /存放商，aResult0對應于個位參考程序int main() int t, n; scanf(%d, &n); for( t = 0; t = 0 ; i -) an1j+ = szLine1i - 0; int nLen2 = strlen(szLine2); for( j = 0, i = nLen2 - 1;i = 0 ; i -) an2j+ = szLine2i - 0; if( nLen1 0) for( i = nLen1 -1; i

16、 = nTimes; i - ) an2i = an2i-nTimes;/朝高位移動 for( ; i = 0; i-)/低位補0 an2i = 0; nLen2 = nLen1; for( j = 0 ; j = 0) nLen1 = nTmp; aResultnTimes-j+; /每成功減一次，則將商的相應位加1 參考程序 /下面輸出結果，先跳過高位0 for( i = MAX_LEN ; (i = 0) & (aResulti = 0); i - ); if( i = 0) for( ; i=0; i-) printf(%d, aResulti); else printf(0); pr

17、intf(n); return 0;參考程序/長度為 nLen1 的大整數p1 減去長度為nLen2 的大整數p2/結果放在p1 里，返回值代表結果的長度，如不夠減返回-1，正好減完返回 0int Substract( int * p1, int * p2, int nLen1, int nLen2) int i; if( nLen1 = 0; i - ) if( p1i p2i ) break; /p1p2 else if( p1i p2i ) return -1; /p1p2 for( i = 0; i =nLen2 時，p2i 0 p1i -= p2i; if( p1i = 0 ; i-

18、 ) if( p1i )/找到最高位第一個不為0 return i + 1; return 0;/全部為0，說明兩者相等麥森數問題描述 形如2P-1 的素數稱為麥森數，這時P 一定也是個素數。但反過來不一定，即如果P 是個素數， 2P-1 不一定也是素數。到1998 年底，人們已找到了37 個麥森數。最大的一個是P=3021377，它有909526 位。麥森數有許多重要應用，它與完全數密切相關。 你的任務：輸入P (1000P3100000) , 計算2P-1 的位數和最后500 位數字（用十進制高精度數表示）問題描述輸入數據只包含一個整數P(1000P3100000)輸出要求第1 行：十進制

19、高精度數2P-1的位數。 第2-11 行：十進制高精度數2P-1 的最后500位數字。（每行輸出50 位，共輸出10 行，不足500 位時高位補0）不必驗證2P-1 與P 是否為素數。輸入樣例1279問題描述輸出樣例386000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0 9673360298012 38356624832346 0 3457731833496 47548478866962 416585028255

20、60 10266984354887 55703168729087第一個問題，輸出2p-1 有多少位。由于2p的個位數只可能是2, 4, 6, 8 所以2p-1 和2p的位數相同。使用log10(double x) 函數，就能輕松求得2p-1 的位數。2的冪可以轉化成左移運算，為了提高運算速度，可每次左移10位，即每次乘210。對于個位單獨考慮，每次左移一位。解題思路1#include #include #define MAX 100000 main() int p; int i, j; scanf(%d, &p); printf(%dn, (int)(p * log10(2.0) + 1);

21、long store110 = 0; store0 = 1; int left = p % 10; p /= 10; for(i = 1; i = p; i+) for(j = 0; j = 100; j+) storej = 10; for(j = 0; j = MAX) storej + 1 += storej / MAX; storej %= MAX; for(i = 1; i = left; i+) for(j = 0; j = 100; j+) storej = 1; for(j = 0; j = MAX) storej + 1 += storej / MAX; storej %=

22、MAX; store0 -= 1; for(i = 1; i 100; i+) if(storei - 1 = 0; i-) printf(%05d, storei); if(100 - i) % 10 = 0) printf(n); 2p 的值可以用一種高效率的辦法來算。顯然，對于任何p0，考慮p 的二進制形式，則不難得到：這里，ai 要么是1，要么是0。解題思路2 因而： 計算2p 的辦法就是：先將結果的值設為1，計算21。如果a0 值為1，則結果乘以21；計算22，如果a1 為1，則結果乘以22；計算24，如果a2 為1，則結果乘以24；總之，第i 步(i 從0 到n，an 是1)就計算

23、22i，如果ai 為1，則結果就乘以22i。每次由22i22i就能算出22(i+1)。由于p可能很大，所以上面的乘法都應該使用高精度計算。由于題目只要求輸出500 位，所以這些乘法都是只須算出末尾的500 即可。解題思路2在前面的高精度計算中，我們用數組來存放大整數，數組的一個元素對應于十進制大整數的一位。本題如果也這樣做，就會超時。為了加快計算速度，可以用一個數組元素對應于大整數的4 位，即將大整數表示為10000 進制，而數組中的每一個元素就存放10000 進制數的1 位。例如，用int 型數組 a 來存放整數6373384，那么只需兩個數組元素就可以了，a0=3384, a1=637。由

24、于只要求結果的最后500 位數字，所以我們不需要計算完整的結果，只需算出最后500 位即可。因為用每個數組元素存放十進制大整數的4 位，所以本題中的數組最多只需要125 個元素。解題思路24、參考程序#include #include #define LEN 125 /每數組元素存放4 位，數組最多需要125 個元素#include int main(void) int i; int p; int anPowLEN; /存放不斷增長的2 的次冪 int aResultLEN; /存放最終結果的末500 位 scanf(%d, & p); printf(“%dn”, (int)(p*log10(

25、2.0)+1); /下面將2 的次冪初始化為2(20)(ab 表示a 的b 次方)， / 最終結果初始化為1 anPow0=2; aResult0=1; for (i=1;i0) /下面計算2 的p 次方 / p = 0 則說明p 中的有效位都用過了，不需再算下去 if ( p & 1 ) /判斷此時p 中最低位是否為1 Multiply(aResult, anPow); p=1; Multiply(anPow, anPow); 參考程序 aResult0-; /2p-1 /輸出結果 for (i=LEN-1;i=0;i-) if (i%25=12) printf(%02dn%02d, aRe

26、sulti/100, aResulti%100); else printf(%04d, aResulti); if (i%25=0) printf(n); return 0;參考程序/計算高精度乘法 a * b, 結果的末500 位放在a 中void Multiply(int* a, int* b) int i, j; int nCarry; /存放進位 int nTmp; int cLEN; /存放結果的末500 位 memset(c, 0, sizeof(int) * LEN); for (i=0;iLEN;i+) nCarry=0; for (j=0;jLEN-i;j+) nTmp=ci

27、+j+aj*bi+nCarry; ci+j=nTmp%10000; nCarry=nTmp/10000; memcpy( a, c, LEN*sizeof(int); 在計算機上進行高精度計算，首先要處理好以下幾個基本問題： 1、數據的接收與存儲；2、計算結果位數的確定； 3、進位處理和借位處理；4、商和余數的求法； 小結能表示多個數的數據類型有兩種：數組和字符串。數組：每個數組元素存儲1位，有多少位就需要多少個數組元素；優(yōu)點：每一位都是數的形式，可以直接加減；運算非常方便缺點：數組不能直接輸入；輸入時每兩位數之間必須有分隔符，不符合數值的輸入習慣；字符串：優(yōu)點：能直接輸入輸出，輸入時，每兩位

28、數之間不必分隔符，符合數值的輸入習慣；缺點：字符串中的每一位是一個字符，不能直接進行運算，必須先將它轉化為數值再進行運算；運算時非常不方便綜合以上所述，對上面兩種數據結構取長補短：用字符串讀入數據，用數組存儲數據。接收和存儲兩數之和的位數最大為較大的數的位數加1。乘積的位數最大為兩個因子的位數之和。階乘：lgn!=lgn+lg(n-1)+lg(n-2).+lg3+lg2+lg1=lnn/ln10+ln(n-1)/ln10+ln(n-2)/ln10+.+ln3/ln10+ ln2/ln10+ln1/ln10=trunc(1/ln10*(lnn+ln(n-1)+ln(n-2)+.+ln3+ln2+

29、ln1)乘方：lg(ab)=trunc(lg(ab)+1=trunc(b*lga)+1=trunc(b*lna/ln10)+1計算結果位數的確定存儲順序： 正序？ 逆序？初始化：一定不要忘了初始化！實際編程時，不一定要費心思去把數組大小定得正好合適，稍微開大點也無所謂，以免不小心沒有算準這個“正好合適”的數值，而導致數組小了，產生越界錯誤。注意的幾個細節(jié)作業(yè)題3. 計算2 的N 次方任意給定一個正整數N(N=100)，計算2 的N 次方的值。4. 浮點數加法求2 個不超過100 位的浮點數相加的和5.浮點數求高精度冪有一個實數 R ( 0.0 R 99.999 ) , 要求寫程序精確計算 R

30、的 n 次方。n 是整數并且0 n = 25。下周四晚前發(fā)到郵箱 .while(scanf(%s%d,d,&n)!=EOF) int a150=0,b150=0,c150=0. int temp,flag,i,j,k,digit,s; int lend,lena,lenb,lenc,len; lend=strlen(d)-1; for(i=0;di;i+) if(di=.)break; digit=lend-i; for(j=i;dj;j+) dj=dj+1; lend=lend-1; for(i=0;i=lend/2;i+) temp=di;di=dlend-i; dlend-i=temp;

31、for(i=0;di;i+) ai=di-48;lena=lend;for(i=0;i=lena;i+)bi=ai;lenb=lena; for(i=1;i=n-1;i+) for(j=0;j=lenb;j+) for(k=0;k=lena;k+) cj+k+=ak*bj; ck+j+1+=cj+k/10; cj+k%=10; k-; j-; if(ck+j+1!=0) lenc=j+k+1; else lenc=j+k; for(j=0;j=0;i-) if(bi!=0)flag=1;break; if(flag=0) for(i=lenb;i=lenb-len+1;i-)printf(%d

32、,bi); printf(n); continue; if(len=1&blenb=0) printf(.); else for(i=lenb;i=lenb-len+1;i-)printf(%d,bi); printf(.); for(i=0;i=temp;i-) printf(%d,bi); printf(n); 思考2.計算n! 。一個例子：計算5*6*7*8方法一：順序連乘5*6=30，1*1=1次乘法30*7=210，2*1=2次乘法210*8=1680，3*1=3次乘法方法二：非順序連乘5*6=30，1*1=1次乘法7*8=56，1*1= 1次乘法30*56=1680，2*2=4次乘

33、法 若“n位數*m位數=n+m位數”，則n個單精度數。無論以何種順序相乘，乘法次數一定為n(n-1)/2次。（n為積的位數）證明：設F(n)表示乘法次數，則F(1)=0，滿足題設設kn時，F(xiàn)(k)=k(k-1)/2，現(xiàn)在計算F(n)設最后一次乘法計算為“k位數*(n-k)位數”，則F(n)=F(k)+F(n-k)+k (n-k)=n(n-1)/2（與k的選擇無關）考慮k+t個單精度數相乘 a1*a2*ak *ak+1*ak+t設a1*a2*ak結果為m位高進制數（假設已經算出）ak+1*ak+t結果為1位高進制數若順序相乘，需要t次“m位數*1位數” ，共mt次乘法可以先計算ak+1*ak+t，再一起乘，只需要m+t次乘法 在設置了緩存的前提下，計算m個單精度數的積，如果結果為n位數，則乘法次數約為n(n1)/2次，與m關系不大設S=a1*a2*am，S是n位高進制數可以把乘法的過程近似看做，先將這m個數分為n組，每組的積仍然是一個單精度數，最后計算后面這n個數的積。時間主要集中在求最后n個數的積上，這時基本上滿足“n位數*m位數=n+m位數”，故乘法次數可近似的看