高精度運算
本節(jié)概要
高精度運算涉及高精度加法，高精度減法，高精度乘法，高精度除低精度，高精度除高精度 5類。以下的講解中，不考慮負數(shù)的情況；除法運算中，我們規(guī)定除數(shù)小于被除數(shù)；規(guī)定高精度數(shù)字的位數(shù)不超過200。
- 本節(jié)內(nèi)容
- 高精度數(shù)字的輸入和存儲方法
- 高精度加法
- 高精度減法
- 高精度乘法
- 高精度除低精度
- 高精度除高精度
- 總結
1. 高精度數(shù)字的輸入和存儲方法
輸入
單個高精度數(shù)字可能長達200位，可以通過兩種方式讀入：1. 單字符讀取、判斷并存儲，直到遇到“\n”(換行符)，可以使用scanf("%c", &c)，或c=getchar()這種方法麻煩；2. 將數(shù)字作為字符串讀入，存入字符數(shù)組中，這種方法最簡單、高效：scanf("%s", temp);
存儲
字符到數(shù)字：使用字符數(shù)組存儲容易，但計算比較麻煩，因數(shù)字在字符數(shù)組中是以字符0～9的形式存在（ASCII碼范圍：48～57），將所有數(shù)位以數(shù)字0～9的形式轉存在一個int數(shù)組中會方便運算。N=='N'-'0'可以實現(xiàn)字符N到數(shù)字N的轉換。
反序存放：使用豎式做加法運算時，規(guī)則是最低位和最低位對齊，在int數(shù)組中如果將數(shù)字正序存放，對應計算位的下標就不一樣，不便于計算，因此我們將數(shù)字反序存放在數(shù)組中，就可以使得低位和低位一一對應（下標相同），方便運算，如12345+9987：
//array index 1 2 3 4 5 6 7 8 9
5 4 3 2 1
+ 7 8 9 9
-------------
2 3 3 2 2
//jw 1 1 1 1
//array index是數(shù)組下標，jw代表進位
存儲位數(shù)： 上面的例子并沒有使用數(shù)組的0號單元，這主要是為了方便運算的緣故，例如n位數(shù)字，我們從1循環(huán)至n即可，這樣思路更加清晰。而留下的0號單元剛好可以用來存儲數(shù)組的長度，長度Array[0]=strlen(temp);
代碼示例
void getNum(int num[]){ //數(shù)組初始化和高精度數(shù)字構建
char temp[500];
scanf("%s", temp); //數(shù)字作為字符串讀入
memset(num, 0, sizeof(int)*500);//將數(shù)組的所有字節(jié)置0
num[0]=strlen(temp); //將位數(shù)存于num[0]中
for(int i=1; i<=num[0]; i++) //逆序將每一位存儲于num中
num[i]=temp[num[0]-i]-'0';
return;
}
//使用方法
int main(){
int num1[500];
int num2[500];
getNum(num1);
getNum(num2);
......
return 0;
}
上面的代碼中用到了
memset()，該函數(shù)位于cstring頭文件中，用于內(nèi)存塊的賦值，在例子中起到了初始化數(shù)組的作用
參數(shù)1是內(nèi)存塊的起始地址, num是數(shù)組的名字，即起始地址
參數(shù)2是初始化值，范圍是0～255，因memset是按字節(jié)為單位進行的
參數(shù)3是初始化的字節(jié)數(shù)，sizeof(int)計算出int的字節(jié)數(shù)，乘以數(shù)組大小500
這里若是沒有用
memset進行內(nèi)存塊初始化會導致運算出錯：如果參與計算的數(shù)字A和數(shù)字B位數(shù)不同，高位相加時，小數(shù)字的高位空間的值具有不確定性，如31415+12：
//array index 1 2 3 4 5 6 7 8 9 10 ...
A 5 1 4 1 3
B 2 1 ? ? ?
------------------------
C 7 2 ? ? ?
//jw 0 0 ? ? ?
可見，數(shù)組在使用前全部置0可以避免這個問題，你也可以用循環(huán)來解決，當然使用memset更加方便。
2. 高精度加法
思路
按位相加：從兩個數(shù)A、B的低位開始按位相加，一邊加一邊進位，C[i]=A[i]+B[i]+jw，進位是上一次相加產(chǎn)生的。
代碼示例
void jiafa(int A[], int B[], int C[]){ //C=A+B
int i, jw; //i從1循環(huán)至max(A[0], B[0])
for(i=1, jw=0; i<=A[0] || i<=B[0]; i++){
C[i]=A[i]+B[i]+jw; //按位相加
jw=C[i]/10; //求進位
C[i]%=10; //與10求余
}
C[i]=jw; //存放最后一個進位
C[0]=C[i] ? i : i-1; //確定C的位數(shù)
return;
}
//使用方法
int main(){
int num1[500];
int num2[500];
int result[500];
getNum(num1);
getNum(num2);
memset(result, 0, sizeof(result)); //在當前函數(shù)中才可以如此計算大小
jiafa(num1, num2, result);
printNum(result); //后面提供函數(shù)代碼
return 0;
}
3. 高精度減法
思路
大小判斷：相減之前要判斷兩個數(shù)A、B的大小關系，如果A>B，則計算A-B，否則計算B-A，需要編程實現(xiàn)大小判斷。
按位相減：從兩個數(shù)A、B的低位開始按位相減，如果L[i]<R[i]，就需要向高位借位，因為我們已經(jīng)確定了左數(shù)字L大于右數(shù)字R，一定能借到。 if(L[i]<R[i]){ C[i]=L[i]+10-R[i]; L[i+1]--;}
確定有效位：按位減完后，高位有可能變?yōu)?，如1000-990后等于10，這時就要重新計算確定結果的有效位數(shù)C[0]是多少。可以從位置max(L[0], R[0]開始倒推，直至遇到非0值停止，這時的位置就是有效位數(shù)。
代碼示例
bool compare(int L[], int R[]){ //實現(xiàn)兩個高精度數(shù)字的大小比較
if(L[0]>R[0]) return true; //位數(shù)高的大
if(L[0]<R[0]) return false; //位數(shù)低的小
int i;
for(i=L[0]; i>=1; i--){ //位數(shù)相同逐位比較
if(L[i]>R[i]) return true; //數(shù)字大的大
if(L[i]<R[i]) return false; //數(shù)字小的小
}
return true; //能執(zhí)行到這里說明相等，返回true
}
void jianfa(int L[], int R[], int C[]){ //C=L-R
for(int i=1; i<=L[0]; i++)
C[i]=L[i]; //把L的所有數(shù)位復制到C
C[0]=L[0]; //C的位數(shù)暫等于L的位數(shù)
int i;
for(i=1; i<=R[0]; i++){ //右值有多少位，就減多少次
if(C[i]<R[i]){
C[i+1]--; //向高位借1
C[i]+=10; //當前位+10
}
C[i]-=B[i]; //按位減
}
if(i<C[0]) return; //計算有效位數(shù)：L[0]-R[0]>=2
else{ //計算有效位數(shù)：L[0]-R[0]==1 or 0
while(C[i]==0 && i>=1) i--;
A[0]=(i==0) ? 1 : i; //例如10000-9999
}
return;
}
//使用方法
int main(){
int num1[500];
int num2[500];
int result[500];
getNum(num1);
getNum(num2);
memset(result, 0, sizeof(result));
if(compare(num1, num2)) jianfa(num1, num2, result);
else jianfa(num2, num1, result);
printNum(result);
return 0;
}
4. 高精度乘法
思路
類似加法，可以用豎式求乘法，同樣也有進位，對每一位進行乘法運算時，必須進行錯位相加：如856×25，見如下規(guī)律：
//array index 1 2 3 4 5 6 7 8 9 ...
A 6 5 8
B 5 2
----------------------------------
0 8 2 4
2 1 7 1
----------------------------------
0 0 4 1 2
//array index 1 2 3 4 5 6 7 8 9 ...
A a1 a2 a3 a4
B b1 b2
----------------------------------
C c1 c2 c3 c4
c2 c3 c4 c5
//本例中未寫出進位
綜上分析，乘法要進行B[0]輪，每輪要進行A[0]次乘法和進位運算，這就找到了循環(huán)的規(guī)律。結合錯位相加，可知C[i+j-1]=C[i+j-1]+A[i]*B[i]+jw，進位jw=c[i+j-1]/10
有效位數(shù)：計算完成后，需要確定結果的有效位數(shù)，使用和減法類似的方法從可能的最大位數(shù)往后推，直到遇到非0的數(shù)位，當前位置就是有效位數(shù)。對于M位的數(shù)字A和N位的數(shù)字B向乘，最大位數(shù)為M+N。
代碼示例
void chengfa(int A[], int B[], int C[]){ //C=A*B
int i,j;
for(i=1; i<=B[0]; i++){ //B[0]輪乘法
int jw; //進位
for(j=1, jw=0; j<=A[0]; j++){ //每輪按位乘A[0]次
C[i+j-1]=C[i+j-1]+A[j]*B[i]+jw; //錯位相加
jw=C[i+j-1]/10; //求進位
C[i+j-1]%=10; //進位后，與10求余
}
C[i+A[0]]=jw; //存儲最后一個進位
}
int len=A[0]+B[0]; //最大可能位數(shù)
while(C[len]==0 && len>1) len--; //確定有效位數(shù)
C[0]=len;
return;
}
//使用方法
int main(){
...
chengfa(num1, num2, result);
printNum(result);
return 0;
}
5. 高精度除低精度
思路
高精度初低精度采用豎式思想，由于除數(shù)是低精度，最后的商可能是高精度，余數(shù)一定為低精度。
商有效位數(shù)：M位的數(shù)字A除以N位的數(shù)字B，商的位數(shù)最大為M-N+1,因為B是低精度數(shù)字，計算長度N比較麻煩，簡單起見，也可以認為商的最大位數(shù)為M, 從最大數(shù)位往后推，直到遇到非0的數(shù)位，當前位置就是有效位數(shù)。
以下是一個模擬計算過程的例子，113056/23：
//
被除數(shù)數(shù)位 當前位數(shù)字 過程被除數(shù) 過程除結果
i=6 1 1/23 商：0
i=5 1 11/23 商：0
i=4 3 113/23 商：4，余：21
i=3 0 210/23 商：9，余：3
i=2 5 35/23 商：1，余：12
i=1 6 126/23 商：5，余：11
//計算結果 商：4915， 余數(shù)：11
代碼示例
void chuDi(int A[], int B, int C[], int &yushu){ //A/B=C 余數(shù)：yushu
int i, t; //t為過程被除數(shù)
for(i=A[0], t=0; i>=1; i--){ //從被除數(shù)高位循環(huán)到低位
t=t*10+A[i]; //更新t
C[i]=t/B; //計算C[i]
t%=B; //更新t
}
yushu=t; //計算完后t就是余數(shù)
i=A[0]; //計算C有效位數(shù)
while(C[i]==0 && i>1) i--;
C[0]=i;
return;
}
//使用方法
int main(){
int num1[500];
int num2;
int shang[500];
int yushu;
getNum(num1);
scanf("%d", num2);
chuDi(num1, num2, shang, yushu);
printNum(shang);
count<<" "<<yushu;
return 0;
}
6. 高精度除高精度
思路
高精度除高精度是這幾種運算中最難的一種。仍然可以模仿豎式的方式進行，過程有點兒麻煩。另一種辦法是利用減法：被除數(shù)A-除數(shù)B，看看能減多少個，直到A<B，這時剪去的個數(shù)就是商，剩下的A就是余數(shù)。如果利用前面編寫好的高精度減法jianfa()和compare()的話，實現(xiàn)起來豈不是很容易？可惜不是這樣，假設被除數(shù)A的位數(shù)M與除數(shù)B位數(shù)N之差M-N很大，這個范圍有可能從0～200，按照最大的情況200考慮，這意味著商值也是高精度數(shù)字，而你要減10^200次才能減完，這是一個天文數(shù)字。
所以，明白否？解決這個問題也很簡單，我們不一個一個減，而是按照最大可能的數(shù)量級減，例如：12345/45：
//商的最大位數(shù)i=M-N+1，即4，設計一個 臨時減數(shù)，減數(shù)后面補齊i-1個0，再進行減法
i=4 12345 < 45000 可以減0個 shang[4]=0 減后A：12345
i=3 12345 < 4500 可以減2個 shang[3]=2 減后A：3345
i=2 3345 < 450 可以減7個 shang[2]=7 減后A：195
i=1 195 < 45 可以減4個 shang[1]=4 減后A：15
//因shang[4]=0，故商的有效位數(shù)shang[0]--，為3
//結果 商為274，余數(shù)15
看明白了嗎，這樣的計算過程，僅僅減了2+7+4=13次，而非274次，可見一個一個減是絕對不靠譜的。下面提供了代碼，注意：減法函數(shù)jianfa()被修改了，使得直接把結果存入A中，而不需要存在另一個數(shù)組C中，這是為了簡化后面運算的緣故。
代碼示例
void jianfa(int A[], int B[]){ //修改了的減法，使得直接在A數(shù)組上減
int i; //不再需要存在數(shù)組C，簡化后面的運算
for(i=1; i<=B[0]; i++){
if(A[i]<B[i]){
A[i+1]--; //向高位借1
A[i]+=10; //當前位+10
}
A[i]-=B[i]; //按位減
}
if(i<A[0]) return; //計算有效位數(shù)
else{
while(A[i]==0 && i>=1) i--;
A[0]=(i==0)? 1 : i;
}
return;
}
//shang=A/B, yushu為余數(shù)
bool chuGao(int A[], int B[], int shang[], int yushu[]){
memset(shang, 0, sizeof(int)*300); //初始化shang
memset(yushu, 0, sizeof(int)*300); //初始化yushu
shang[0]=A[0]-B[0]+1; //商的最大數(shù)位
for(int i=shang[0]; i>=1; i--){ //從高位到低位開始計算商
int jianshu[300]; //構造要減的減數(shù)
memset(jianshu, 0, sizeof(jianshu));
//這個函數(shù)下面有解釋
memcpy(jianshu+i, B+1, sizeof(int)*B[0]);
jianshu[0]=B[0]+i-1; //確定減數(shù)的位數(shù)
while(compare(A, jianshu)){ //通過循環(huán)減
jian(A, jianshu);
shang[i]++; //減去一個商的對應為+1
}
}
if(shang[shang[0]]==0) shang[0]--; //判斷商的最高位是否有效
memcpy(yushu, A, sizeof(int)*300); //A就是余數(shù)，把它完全復制給yushu
}
//使用方法
int main(){
int num1[300]; //數(shù)組A存儲第1個數(shù)字信息
int num2[300]; //數(shù)組B存儲第2個數(shù)字信息
int shang[300];
int yushu[300];
init(num1);
init(num2);
chuGao(num1, num2, shang, yushu);
print(shang);
printf(" ");
print(yushu);
return 0;
}
上面的代碼中用到了memcpy()，該函數(shù)位于cstring頭文件中，用于內(nèi)存塊之間的復制
參數(shù)1是destination，即復制的目的地，為一地址
參數(shù)2是source，即復制數(shù)據(jù)的來源，為一地址
參數(shù)3是要復制的字節(jié)數(shù)，sizeof(int)計算出int的字節(jié)數(shù)，乘以相應的元素個數(shù)N例程中的
memcpy(jianshu+i, B+1, sizeof(int)*B[0])是從B數(shù)組的1號位置開始（跳過B[0]），復制B[0]個數(shù)位，目的地為jianshu數(shù)組的第jianshu+1+i-1個位置，+1是為了跳過jianshu[0]，+i-1是把這幾個位置空成0，以構造最大數(shù)量級的減數(shù)。暈了么有？別怕，其實可以把代碼寫的長一些，但是更簡單一些的，這里是偷懶了;-)
7. 總結
用途
高精度運算在信息學奧賽計算中常常出現(xiàn)，因此必須掌握。例如計算大型斐波那契數(shù)列、計算高階次冪、計算N!等，如果不使用高精度進行計算，內(nèi)存溢出是必然結果。
最后提供print()函數(shù)，十分簡單，你應該可以自己寫出來:-)
代碼示例
void print(int X[]){ //輸出高精度數(shù)字
for(int i=X[0]; i>=1; i--) printf("%d", X[i]);
return;
}
浙公網(wǎng)安備 33010602011771號