C++大整数运算(四):除法

0

C++大整数运算系列文章讲述了实现大整数四则运算的基本思路和方法,对算法做简单的介绍并采用C++代码做进一步说明。本文并不试图写成一篇教程,而是对实现过程进行整理和概括。实现过程中学习了 Donald E. Knuth 著作的 The Art of Computer Programming 中的相关内容,特此致敬。

本文是C++大整数运算系列文章的第四篇,主要介绍如何实现大整数运算的除法运算。

目录

除法是乘法的逆运算,计算复杂度要比乘法高出很多,如果从效率的角度考虑,宁可多算几次乘法,也不算一次除法。一般来说,在计算机中计算大整数除法,实际上也是模拟手工除法的过程,即多次采用乘法和减法来计算每个数位上的商。

本文计算除法运算基本按照Knuth著作的TAOCP中第三版第四章描述的思路。首先来看商是一个数位的情况。

假设被除数表示为:\(u = u_n u_{n-1} \cdots u_1 u_0\),除数表示为\(v = v_{n-1} \cdots v_1 v_0\),u和v为2^32进制的整数,u = q*v + r,其中0<=q<2^32,0<=r<v。如果不考虑效率的话,枚举也好,二分也好,总能算出q的值,但显然这样算还是太慢了。Knuth在TAOCP中给出一个定理:如果\(v_{n-1} \geq base/2\),且\(\hat q = min((u_n * base + u_{n-1})/v_{n-1}, base-1)\),则\(\hat q – 2 \leq q \leq \hat q\),其中\(\hat q\)是q的估计值。这个定理表明,最多只需要计算三次乘法,就能得到商的准确值。

有了计算一位数除法的方法,就可以按照手工除法的方式计算大整数除法,具体计算流程如下:
给定非负整数\(u=u_{m+n-1} \cdots u_1 u_0, v=v_{n-1} \cdots v_1 v_0, v_{n-1} \gt 0, n \gt 1\)。
1. 规格化
定理要求\(v_{n-1} \geq base/2\),置\(d = base/(v_{n-1} + 1)\),然后令u=u*d,v=v*d。若进制base为2的幂次,可以直接使用移位操作完成这项工作。
2. 初始化循环变量j = m,第一次循环实际上是\(u_{j+n} \cdots u_{j+1} u_j\)除以v。
3. 计算q的估计值
\(\hat q = (u_{j+n} \times base + u_{j+n-1})/v_{n-1}\)
4. 判断\((u_{j+n} \cdots u_j) – \hat q * v\)是否大于v,若大于则\(\hat q\)减一。最后令\((u_{j+n} \cdots u_j)\)为\((u_{j+n} \cdots u_j) – q \times v\)。
5. j减一,若j不小于0则返回第三步
6. 每一步得到的q组合起来就得到商,而余数通过对\((u_{n-1} \cdots u_0)\)进行与第一步相反的规格化得到。

上述过程并不是书中算法的完整描述,需要进一步研究的读者请参考原书中的内容。
由于作者现在很懒,请到这里查看作者实现的完整的代码
到这里,对于无符号大整数的四则运算已经基本完成,下一节将介绍将十进制字符串转换成大整数以及将大整数转换成十进制字符串的方法。

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注