超长整数的基础运算 算法实现之乘、除篇
来源：程序员人生 发布时间：2014-11-14 08:24:38 阅读次数：2541次
笔算乘法：
对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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
