程序员人生网站导航

超长整数的基础运算算法实现之乘、除篇

栏目：互联网时间：2014-11-14 08:24:38

笔算乘法：

对m位和n位的输入，传统的乘法需要mn次基本的乘法，也即算法复杂度为O()。我们用纸和笔做乘法运算时，用乘数的每位乘以被乘数的每位并加上上1列的进位而产生1行适当移位的中间结果，然后再将各行中间结果相加即得到乘法的终究结果，例如10进制下计算18934的进程以下表：

笔算乘法的运算进程

本算法依照上述进程进行计算，但在计算机上最好是把内部的乘法和加法并行的履行，即计算每行中间结果的同时将该行加到终究结果上，这样既可以省去很多步骤，也避免了中间结果的空间开消和内存管理操作，这个简单的优化能够1定程度上提高效力。本算法的伪代码以下表：

输入：分别含有n和t个B进制数位的大整数x、y

输出：B进制的乘积

1. i从0到n+t⑴,置W_i = 0

2. i从0到t

2.1 j从0到n

计算w_i+j=w_i+j + x_j * y_i

若 w_i+j 不小于进位值，

则重新格式化当前中间值表示

3. 返回

由于两个16位的乘积将超过16位所能表示的最大数，我们知道1个32位的数能够完全地保存两个16位数的乘积，上面的伪码中用1个32位来保存两个16位的数乘积再加上两个单字后的结果，下面讨论1下它的安全性（是不是会产生溢出）：上面表达式计算的最大的结果为(2¹⁶ - 1)*(2¹⁶- 1) + (2¹⁶ - 1)，化简后为2³² - 2¹⁶，小于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个难点就是对除数进行位对齐。多数操作中，除数的位数小于被除数，所以在进行试商前需要对除数进行左移，即人为扩大除数的倍数（Bⁿ）。至于左移具体几位，需要对高位进行比较后肯定，规则以下：

输入：两个B进制（位数M、N）的大整数x（除数）、y（被除数）

x=m₁m₂..m_M，y=n₁n₂…n_N

输出：左移位数L

1. 默许情况下M < N，故初始化L=N-M

2. 比较两个数的高位部份：

2.1 比较m₁与 n₁

若m₁ > n₁ 则L=L⑴

若m₁ = n₁ 则置i从0..L

若m_i> n_i则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; }

------分隔线----------------------------

上一篇 使用Xshell生成key,免密码登录linux

下一篇 《程序员跳槽全攻略》读后总结

------分隔线----------------------------