高精度運(yùn)算(C++)

1、萬進(jìn)制高精度運(yùn)算（C+語言）目前在青少年信息學(xué)奧林匹克競賽中所涉及到的高精度計(jì)算包括加(addition)、減(subtract)、乘(multiply)、除(divide)四種基本運(yùn)算。其中乘法分高精度數(shù)乘高精度數(shù)和單精度數(shù)乘高精度數(shù)兩種，除法一般指兩個(gè)單精度數(shù)相除，求解最終指定精度的解，找出循環(huán)節(jié)或輸出指定精度位數(shù)的小數(shù)。（注：高精度數(shù)與單精度數(shù)均指整數(shù)）主要的解題思想是利用在小學(xué)就曾學(xué)習(xí)過的豎式加減乘除法則，用程序語言實(shí)現(xiàn)存在的問題主要有如何存儲(chǔ)高精度數(shù)的值，如何實(shí)現(xiàn)計(jì)算等問題。一. 高精度數(shù)字的存儲(chǔ)我們?nèi)粘鴮懸粋€(gè)高精度數(shù)字，左側(cè)為其高位，右側(cè)為其低位，在計(jì)算中往往會(huì)因進(jìn)位（carry

2、）或借位（borrow）導(dǎo)致高位增長或減少，因此我們定義一個(gè)整型數(shù)組（int bignummaxlen）從低位向高位實(shí)現(xiàn)高精度整數(shù)的存儲(chǔ)，數(shù)組的每個(gè)元素存儲(chǔ)高精度數(shù)中的一位。（如下表所示）高精度數(shù)3（高位）794（低位）int bignumin210顯然，在C+語言中，int類型（4個(gè)字節(jié)/32位計(jì)算機(jī)）元素存儲(chǔ)十進(jìn)制的一位數(shù)字非常浪費(fèi)空間，并且運(yùn)算量也非常大，因此常將程序代碼優(yōu)化為萬進(jìn)制，即數(shù)組的每個(gè)元素存儲(chǔ)高精數(shù)字的四位。在后面的敘述過程中均以萬進(jìn)制為例介紹。（為什么選擇萬進(jìn)制，而不選擇更大的進(jìn)制呢？十萬進(jìn)制中的最大值99999相乘時(shí)得到的值是9999800001超過4個(gè)字節(jié)的存儲(chǔ)范圍而溢

3、出，從而導(dǎo)致程序計(jì)算錯(cuò)誤。）在實(shí)際編寫程序代碼過程中常作如下定義：const int base=10000;const int maxlen=1000+1;int bignummaxlen;說明：base表示進(jìn)制為萬進(jìn)制，maxlen表示高精度數(shù)的長度，1個(gè)元素能存儲(chǔ)4個(gè)十進(jìn)制位，1000個(gè)元素就存儲(chǔ)4000個(gè)十進(jìn)制位，而加1表示下標(biāo)為0的元素另有它用，常用作存儲(chǔ)當(dāng)前高精度數(shù)字的位數(shù)。二. 各種運(yùn)算的程序?qū)崿F(xiàn)（一）加法：首先回顧一下小學(xué)中曾學(xué)習(xí)的豎式加法，見圖一：bignum19475461243bignum29181324341carry1000bignum_ans139313701584圖

4、一 加法的計(jì)算過程從上面的圖中我們可以得知，做加法運(yùn)算是從低位向高位進(jìn)行，如果有進(jìn)位，下一位進(jìn)行相加時(shí)要加上進(jìn)位，如果最高位已計(jì)算完還有進(jìn)位，就要增加存儲(chǔ)結(jié)果的位數(shù)，保存起進(jìn)位來。關(guān)于進(jìn)位的處理，往往定義單獨(dú)變量carry進(jìn)行存儲(chǔ)，程序?qū)崿F(xiàn)的過程如圖二所示：初始化 進(jìn)位carry賦初始值0，結(jié)果的位數(shù)為兩個(gè)加數(shù)的最大位數(shù)。當(dāng)前位超過最高位了？處理當(dāng)前位和進(jìn)位NY還有進(jìn)位么？N結(jié)束處理進(jìn)位Y圖二 加法的實(shí)現(xiàn)過程高精度加法程序代碼（bignum1+bignum2bignum_ans）：void addition(int *bignum1, int *bignum2, int *bignum_ans

5、)int carry=0;memset( bignum_ans, 0, sizeof(bignum_ans) );/ memset作用是在一段內(nèi)存塊中填充某個(gè)給定的值，它是對較大的結(jié)構(gòu)體或數(shù)組進(jìn)行清零操作的一種最快方法。*bignum_ans=*bignum1>*bignu2?*bignum1:*bignum2;for(int pos=1; pos<=*bignum_ans; pos+)carry+=bignum1pos+bignum2pos;bignum_anspos=carry%base;carry/=base;while(carry)bignum_ans+*bignum_an

6、s=carry%base;carry/=base;說明：函數(shù)中的數(shù)組是引用傳遞，傳遞的是數(shù)組的首元素的地址，可用指針來代替，當(dāng)前指針?biāo)赶虻臑?元素，后面的代碼相同。有的同學(xué)可能提出，在加法運(yùn)算中的進(jìn)位不管進(jìn)制是多少，進(jìn)位只可能出現(xiàn)1，用while循環(huán)沒有意義，在這里說明一下，為了跟后面乘法中出現(xiàn)的代碼相匹配才采用這種處理方法，實(shí)現(xiàn)代碼的統(tǒng)一性。（二）減法：bignum11329475461243bignum21329181324341borrow0100bignum_ans085568722902圖三 減法的計(jì)算過程圖三表示出了減法的計(jì)算過程，與加法不同的地方是進(jìn)位變成了借位，另外就是計(jì)算結(jié)

7、果的位數(shù)可能會(huì)比被減數(shù)的位數(shù)少，因此在處理過程中要更要注意結(jié)果到底是多少位的。其次，日常我們做減法時(shí)，如果被減數(shù)小于減數(shù)，我們是把兩數(shù)反過來進(jìn)行相減，在前面添加負(fù)號標(biāo)識。因此，我們在編寫減法子函數(shù)時(shí)是約定bignum1大于bignum2的，調(diào)用時(shí)首先判斷兩個(gè)高精度數(shù)的大小，然后根據(jù)兩數(shù)的大小決定如何調(diào)用。減法的實(shí)現(xiàn)過程如圖四所示：初始化 借位borrow賦初始值0，結(jié)果的位數(shù)為被減數(shù)的位數(shù)。當(dāng)前位超過最高位了？處理當(dāng)前位和借位NY結(jié)果高位為0？N結(jié)束結(jié)果位數(shù)減1Y圖四 減法的實(shí)現(xiàn)過程高精度數(shù)比較程序代碼：int bignumcmp( int *bignum1, int *bignum2 )if

8、 (*bignum1-*bignum2) return *bignum1-*bignum2;for (int pos=*bignum1; pos>0; pos-)if ( bignum1pos-bignum2pos ) return bignum1pos-bignum2pos; return 0;說明：bignum1>bignum2返回正整數(shù)，bignum1bignum2返回0，bignum1bignum2返回負(fù)整數(shù)。解釋：首先進(jìn)行兩數(shù)的位數(shù)的比較，如果位數(shù)相同再從高位向低位比較。高精度減法程序代碼（bignum1-bignum2bignum_ans）：void subtract(

9、 int *bignum1, int *bignum2, int *bignum_ans )int borrow=0;memset( bignum_ans, 0, sizeof(bignum_ans) );*bignum_ans=*bignum1;for(int pos=1; pos<=*bignum_ans; pos+)bignum_anspos=bignum1pos-borrow-bignum2pos;if(bignum_anspos<0)bignum_anspos+=base;borrow=1;elseborrow=0;while( !bignum_ans*bignum_an

10、s ) -*bignum_ans;（三）乘法：乘法的計(jì)算過程正如圖五所示的從乘數(shù)的最低位起枚舉每一位與被乘數(shù)相乘，累加到結(jié)果當(dāng)中。高精度乘高精度實(shí)際是多次調(diào)用單精度數(shù)乘高精高數(shù)運(yùn)算。1234X4321(1)1234(2)2468(3)3702(4)49365332114圖五 乘法的計(jì)算過程首先看一下單精度數(shù)乘高精度數(shù)的實(shí)現(xiàn)過程，如圖六所示：初始化 進(jìn)位carry賦初始值0，結(jié)果的位數(shù)被乘數(shù)的位數(shù)。當(dāng)前位超過最高位了？處理當(dāng)前位和進(jìn)位NY還有進(jìn)位么？N結(jié)束處理進(jìn)位Y圖六 單精度乘高精度實(shí)現(xiàn)過程單精度乘高精度程序代碼（n*bignumbignum_ans）：void SingleMultiply(

11、int n, int *bignum, int *bignum_ans)int carry=0;memset(bignum_ans, 0, sizeof(bignum_ans);*bignum_ans=*bignum;for(int pos=1; pos<=*bignum_ans; pos+)carry+=n*bignumpos;bignum_anspos=carry%base;carry/=base;while(carry)bignum_ans+*bignum_ans=carry%base;carry/=base;高精度數(shù)乘高精度數(shù)，實(shí)質(zhì)就是在單精度數(shù)乘高精度數(shù)的基礎(chǔ)上枚舉各個(gè)乘數(shù)位與

12、被乘數(shù)相乘，累計(jì)到結(jié)果當(dāng)中。其中乘數(shù)中的第J位與被乘數(shù)中的第I位相乘時(shí)，結(jié)果應(yīng)該保存到結(jié)果的第IJ1位中，因?yàn)槿绻嬖谶M(jìn)位的問題結(jié)果的位數(shù)可能為乘數(shù)與被乘數(shù)的位數(shù)和，也可能為兩者位數(shù)和減一，這一點(diǎn)也應(yīng)該單獨(dú)處理。過程就不再展示了，具體的請閱讀下面的程序代碼：高精度乘高精度程序代碼（bignum1*bignum2bignum_ans）：void BignumMultiply( int *bignum1, int *bignum2, int *bignum_ans)int carry=0, i, j;memset(bignum_ans, 0, sizeof(bignum_ans) );for (j

13、=1; j<=*bignum2; j+)for(i=1; i<=*bignum1; i+)bignum_ansi+j-1+=carry+bignum1i*bignum2j;carry=bignum_ansi+j-1/base;bignum_ansi+j-1%=base;i=j+*bignum1;while(carry)bignum_ansi+=carry%base;carry/=base;*bignum_ans=*bignum1+*bignum2;while( !bignum_ans*bignum_ans ) -*bignum_ans;（四）除法：除法在高精度計(jì)算中是最為特殊的，在

14、近幾年聯(lián)賽中并沒有出現(xiàn)類似的題目，除法類的高精度題目會(huì)涉及到精度和循環(huán)節(jié)問題，在這里首先用表格分析兩個(gè)例子：例一：3除以8，結(jié)果為0.375被除數(shù)3306040商0.375余數(shù)3640例二：45除以56，結(jié)果為0.803(571428)被除數(shù)454502020032040080240160480商0.803571428余數(shù)452203240824164832在例一中展示的為能被除盡的情形，能被除盡的條件是余數(shù)為0，而在例二中56并不能除盡45，出現(xiàn)571428這個(gè)循環(huán)節(jié)，出現(xiàn)循環(huán)節(jié)的條件是當(dāng)前的余數(shù)曾經(jīng)出現(xiàn)在前面求得的余數(shù)序列中。直接模擬除法操作進(jìn)行程序設(shè)計(jì)的過程如圖七所示：初始化 商存儲(chǔ)數(shù)組

15、quotient清零，余數(shù)數(shù)組remainder清零。余數(shù)為0？處理當(dāng)前位NY結(jié)束 輸出整除值，存儲(chǔ)余數(shù)余數(shù)序列中出現(xiàn)過么？處理循環(huán)節(jié)YN圖七 高精度除法實(shí)現(xiàn)過程根據(jù)上述處理過程編寫代碼如下：void divide(int x, int y)int remaindermaxlen, quotientmaxlen, repeat_pos=-1, pos=0;quotient0=x/y;remainder0=x%y;while( remainderpos )for(int i=0; i<pos; i+)/查找余數(shù)序列if(remainderi=remainderpos)repeat_pos=

16、i; break; if(repeat_pos>-1) break;pos+;if(pos=maxlen) pos-; break; /是否已到求解的精度remainderpos=remainderpos-1*10%y;quotientpos=remainderpos-1*10/y;cout<<quotient0;if(remainder0)cout<<'.'int i=1;if(repeat_pos>-1)for(i=1; i<=repeat_pos; i+) cout<<quotienti;cout<<

17、9;('while(i<=pos) cout<<quotienti+;if(repeat_pos>-1) cout<<')'cout<<endl;說明：maxlen為指定的精度或最大的小數(shù)位數(shù)加一，根據(jù)程序需要而定義。從上面的程序可以看出，在求得每一個(gè)余數(shù)后，都要到前面的余數(shù)序列中查找是否已存在，來判定是否出現(xiàn)循環(huán)節(jié)，這種方法即費(fèi)時(shí)又浪費(fèi)空間。有沒有更好的方法來解決這個(gè)問題呢？我們從數(shù)學(xué)上的自然數(shù)找一下規(guī)律。任何一個(gè)自然數(shù)都可拆分為若干質(zhì)數(shù)的冪的形式（n=p1K1*p2K2pnKn），在所有的質(zhì)數(shù)中，只有2和5才能被除盡，

18、其他的均出現(xiàn)循環(huán)節(jié)。我們是否可以從2和5上找出解決方法來呢？將被除數(shù)和除數(shù)轉(zhuǎn)化為互質(zhì)的兩個(gè)數(shù)，從除數(shù)中統(tǒng)計(jì)出2和5的個(gè)數(shù)n2和n5，且一個(gè)2和一個(gè)5都僅產(chǎn)生一位小數(shù)，這些小數(shù)是肯定不出現(xiàn)在循環(huán)節(jié)中的。反過來說，在小數(shù)點(diǎn)后面，循環(huán)節(jié)前面小數(shù)的位數(shù)就是n2和n5中的較大者。如果求解出循環(huán)節(jié)前的小數(shù)以后，余數(shù)仍不為0，那就存在著循環(huán)節(jié)了，循環(huán)節(jié)的長度為再次得到的這個(gè)余數(shù)。請看下面的代碼：小數(shù)點(diǎn)后循環(huán)節(jié)前的位數(shù)程序代碼：int numBeforeRepeat(int x, int y)int n2=0, n5=0;while(y%2=0)n2+; y/=2;while(y%5=0)n5+; y/=5;

19、while(x%2=0)n2-; x/=2;while(x%5=0)n5-; x/=2;if(n2<n5) n2=n5;return n2>0?n2:0;高精度除法程序代碼：void divide(int x, int y)int BeforeRepeat=numBeforeRepeat(x, y);cout<<x/y; x%=y;if(x)cout<<'.'for(int i=0; i<BeforeRepeat; i+)x*=10;cout<<x/y;x%=y;if(x)cout<<'('int

20、 remainder=x;doremainder*=10;cout<<remainder/y;remainder%=y;while(remainder != x);cout<<')'cout<<endl;利用這種解法一方面省去了余數(shù)和商的存儲(chǔ)空間，另一方面也無需再到余數(shù)序列中查找余數(shù)是否出現(xiàn)過，即節(jié)省空間，又提高了程序的執(zhí)行效率。所以遇到高精度除法問題時(shí)，可以優(yōu)選第二種解法。三. 萬進(jìn)制高精度數(shù)的輸出問題：采用萬進(jìn)制來進(jìn)行高精的加、減、乘三種運(yùn)算，雖然提高了程序的執(zhí)行效率，但在輸出時(shí)卻帶來了問題，如在加法示例中的結(jié)果從高位到低位分別為1，393，1370，1584，如果我們?nèi)园凑掌匠５妮敵鲆粯又苯虞敵鰰r(shí)，結(jié)果為139313701584，但我們定義萬進(jìn)制時(shí)明確過每一