超長整數的基礎運算 算法實現之乘、除篇
來源：程序員人生 發布時間：2014-11-14 08:24:38 閱讀次數：2689次
筆算乘法：
對m位和n位的輸入，傳統的乘法需要m*n次基本的乘法，也即算法復雜度為O()。我們用紙和筆做乘法運算時，用乘數的每位乘以被乘數的每位并加上上1列的進位而產生1行適當移位的中間結果，然后再將各行中間結果相加即得到乘法的終究結果，例如10進制下計算189*34的進程以下表：
筆算乘法的運算進程
本算法依照上述進程進行計算，但在計算機上最好是把內部的乘法和加法并行的履行，即計算每行中間結果的同時將該行加到終究結果上，這樣既可以省去很多步驟，也避免了中間結果的空間開消和內存管理操作，這個簡單的優化能夠1定程度上提高效力。本算法的偽代碼以下表：
|
輸入：分別含有n和t個B進制數位的大整數x、y
輸出：B進制的乘積
|
|
1. i從0到n+t⑴,置Wi = 0
2. i從0到t
2.1 j從0到n
計算wi+j=wi+j + xj * yi
若 wi+j 不小于進位值，
則重新格式化當前中間值表示
3. 返回
|
由于兩個16位的乘積將超過16位所能表示的最大數，我們知道1個32位的數能夠完全地保存兩個16位數的乘積，上面的偽碼中用1個32位來保存兩個16位的數乘積再加上兩個單字后的結果，下面討論1下它的安全性（是不是會產生溢出）：上面表達式計算的最大的結果為(216 - 1)*(216- 1) + (216 - 1)，化簡后為232 - 216，小于1個32位數的最大值，所以1個32位數能夠保存該表達式的結果而不產生溢出，程序不會損失精度。
在乘法中有1類乘法較為特殊--自平方。針對這類乘法使用1般的計算法自然是可行的，但是可以采取更加快捷的方式，使用1次遍歷整數每位做乘法后便可解決1般乘法需要嵌套循環兩次才能處理的結果，由于自平方的兩個乘數是“對稱”的，以A（a1a2a3a4）為例：每位的乘法履行后都會有對應的位重復操作1次，比如a1*a4會履行兩次，而且對應的乘積結果在相同的結果位置上累加。所以在此基礎上自平方的算法效力要比1般乘法要高。
/*
乘法運算
*/
int mulHBInt(HBigInt *product, HBigInt *biA, HBigInt *biB){
HBigInt biT; //計算結果先保存在臨時變量中
register un_short *pWordA = biA->pBigInt;
register un_short *pWordB = biB->pBigInt;
register un_short *pPrd = NULL;
long result = 0, i = 0, j = 0;
//初始化臨時大整數變量
if((result = initHBInt(&biT,biA->length + biB->length)) != RETURN_OK_BINT)
return result;
biT.length = biA->length + biB->length;
biT.sign = (biA->sign == biB->sign) ? 1: ⑴; //同號為正，異號為負
pPrd = biT.pBigInt;
for(i=0; i<biA->length; ++i) { // 按傳統的紙筆乘法的方式計算乘積
for(j=0; j<biB->length; ++j) {
pPrd[i+j] = pPrd[i+j] + pWordA[i] * pWordB[j];
// 如果超越單位長度能表示最大的值（本例中是2<<16）,則進行1次格式化處理
if(pPrd[i+j] >> BIT_PRE_WORD) formatHBInt(&biT);
}
}
//formatHBInt(&biT);
trimHBInt(&biT);//去除高位無效的0
extendHBInt(product,biT.length);
assignHBInt(product,&biT);
deleteHBInt(&biT); //清除臨時變量
return RETURN_OK_BINT;
}
筆算除法：
此算法是摹擬筆算除法的情勢，變形而來。根據筆算除法的特性，我們知道最重要的也是較難的1步是，對商的估算。我們做除法運算，是根據被除數和除數最高幾位來試商的，此算法也是使用這類方式。在試商時，為了提高速度，嘗試使用的商不多是從1開始直到i，i滿足。本運算使用2分查找法來試商，從而提高了速度。
除試商外，另外1個難點就是對除數進行位對齊。多數操作中，除數的位數小于被除數，所以在進行試商前需要對除數進行左移，即人為擴大除數的倍數（Bn）。至于左移具體幾位，需要對高位進行比較后肯定，規則以下：
|
輸入：兩個B進制（位數M、N）的大整數x（除數）、y（被除數）
x=m1m2..mM，y=n1n2…nN
輸出：左移位數L
|
|
1. 默許情況下M < N，故初始化L=N-M
2. 比較兩個數的高位部份：
2.1 比較m1 與 n1
若m1 > n1 則L=L⑴
若m1 = n1 則置i從0..L
若mi > ni則L=L⑴
否則，結束循環
3. 返回L
|
/*
除法運算
a 被除數
b 除數
c 商
d 余數
*/
int divHBInt(HBigInt *a, HBigInt *b, HBigInt *c, HBigInt *d){
HBigInt ta,tb,tc,temp,tc_1; //臨時變量
long result=0,first=1,middle=0,last=0;
un_short mark=0;
long len_ta,len_tb,len,i;
int re;
if(0 == b->length || (1 == b->length && 0 == b->pBigInt[0])) return ⑴; //除數不能為0
//除數為1，則商等于被除數，余數為0
if(1 == b->length && 1 == b->pBigInt[0]) {
assignHBInt(c,a);
setZeroHBInt(d);
hbi_add_int(d,0);
return RETURN_OK_BINT;
}
re = compareHBInt(a,b);
if(⑴ == re) { //除數大于被除數，商為0，余數為被除數
setZeroHBInt(c);
assignHBInt(d,a);
return RETURN_OK_BINT;
}
if(0 == re) { //除數等于被除數，商為1，余數為0
setZeroHBInt(c);
setZeroHBInt(d);
hbi_add_int(c,1);
hbi_add_int(d,0);
return RETURN_OK_BINT;
}
//初始化臨時變量
initHBInt(&ta,INITIAL_BINT);
initHBInt(&tb,INITIAL_BINT);
initHBInt(&tc,INITIAL_BINT);
initHBInt(&temp,INITIAL_BINT);
initHBInt(&tc_1,INITIAL_BINT);
len_ta=ta.length;
len_tb=ta.length;
len=len_ta-len_tb;
i=0;
assignHBInt(&ta,a); //對臨時變量賦值
assignHBInt(&tb,b);
hbi_add_int(&tc,1); //初始商為1
extendHBInt(&temp,ta.length); //擴大臨時變量長度
extendHBInt(&tc_1,ta.length);
//2分法試商計算
while(compareHBInt(&ta,b) > 0 ) { // 保證ta大于b時循環
len_ta=ta.length;
len_tb=tb.length;
len=len_ta-len_tb;
i=0;
mark=0;
if(ta.pBigInt[len_ta⑴] <= tb.pBigInt[len_tb⑴]) {
while(i<len_tb){
if(ta.pBigInt[len_ta⑴-i] < tb.pBigInt[len_tb⑴-i]) {
mark=ta.pBigInt[len_ta⑴];
len--;
i++;
break;
} else i++;
}
}
Left_shift_word(&tb,len); //對除數進行左移位，使其跟被除數有相同數位
Left_shift_word(&tc,len); //商同時左移位
result=mark*CARRY_RADIX+ta.pBigInt[len_ta⑴-i];
first=1;
last= result / tb.pBigInt[len_tb⑴+len] + 1; //2分查找法的上限
middle=(last+first)/2 + 1; //2分查找的中間值
for(; (first < last) && (first != middle); ) { //使用2分查找法來試商
assignHBInt(&temp,&tb);
hbi_mul_radix(&temp,middle);
if(⑴ == compareHBInt(&ta,&temp)) last=middle;
else first=middle;
middle=(last+first)/2;
}
assignHBInt(&temp,&tb);
hbi_mul_radix(&temp,middle);
subHBInt(&ta,&ta,&temp); //被除數-除數*商
hbi_mul_radix(&tc,middle); //得到所試的商
addHBInt(&tc_1,&tc_1,&tc); //對商進行累加
setZeroHBInt(&tc); //臨時保存商的值清0
hbi_add_int(&tc,1); //對商的臨時變量賦1
setZeroHBInt(&temp);
assignHBInt(&tb,b);
}
if(compareHBInt(&ta,b) == 0) {
hbi_add_int(c,1);
setZeroHBInt(d);
} else {
if(c!=NULL) assignHBInt(c,&tc_1); //得到除法運算的商
if(d!=NULL) assignHBInt(d,&ta); //除法運算的余數
}
// 回收臨時變量空間
deleteHBInt(&ta);
deleteHBInt(&tb);
deleteHBInt(&tc);
deleteHBInt(&tc_1);
deleteHBInt(&temp);
return RETURN_OK_BINT;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
