大整数除法之最优估商的理论证明
本帖最后由 只是呼吸 于 2016-4-29 16:42 编辑作为除法中的一种-----估商法，有一定的实际应用，尤其在数字规模不太大的时候是比较有效率的。
本文将在一个特殊的数据结构下，给出估商的最优解。
理论基础： 被除数=商\(\times\)除数+余数，
其中：\(0\leqslant余数<除数。\)
或者
余数=被除数-商\(\times\)除数---------------------------------------------------（1）
其中：\(0\leqslant余数<除数\)-----------------------------------------------------------（2）
（1）和（2）将是我们进行证明的理论基础
约定：1）在计算机中，数组是存入各个存贮单元的，每一个存贮单元只能存\(2^{32}\)(32位系统)，或者存\(2^{64}\)(64位系统)。在这里，我们只讨论32位系统的情况，64位的情况是一样的。
2）本文只讨论十进制的情况，具体一点是\(10^4\)进制。选择\(10^4\)进制是为了在证明过程中少写一点字，但是整个证明的过程对\(10^n\)进制是类似的。
3）每一个存贮单元中存入的十进制数，我们称为一位。
数据结构：1）被除数，每一个存贮单元中存入4个十进制数，记为：\(a_ia_{i+1}a_{i+2}a_{i+3}\)
i=1表示数组的第一位（最高位），有最高的权。它可能不会正好是4位十进制数，但没有关系，这个不会影响我们的结论。
i=2,3----n依次表示数组的第2位、第3位------第n位，这些数一定是4位十进制数充满的。
2）除数，第一个存贮单元中（第一位，它有最高的权）存入5个十进制数，记为：\(b_1b_2b_3b_4b_5\)(\(b_1\geqslant1\))，其余的每4个数进入存贮单元中，记为\(b_{i+4}b_{i+5}b_{i+6}b_{i+7}\) (i=2,3,----m)
i=2表示数组的第2位，-------i=m表示数组的第m位。
大整数的第一位商：按前面约定的数据结构，我们做好下面的三步工作：
1）除数的所有数字都参与运算。现在不妨假设除数的位数为\(m\)位,那么除数的十进制数字个数为\(4m+1\) 个。记为
\(b_1b_2b_{……}b_{4m+1}\)---------------（3）
2）被除数选取\(m+1\)位参与运算，那么参与运算的被除数的数字个数最多为\(4m+4\)个，记为
\(a_1a_2a_{……}a_{4m+4}\)-------------------（4）
3）做除法：记\(s_{大整数商}\)为大整数的商，那么：
\(s_{大整数商}=[\frac{a_1a_2{......}a_{4m+4} }{b_1b_2{......}b_{4m+1} }]\) --------（5）
符号[ ] 是取运算后的整数。
这个\(s_{大整数商}\)就是我们要的大整数的第一位商。但是计算机的字长限制，一个存贮单元不能完整存贮\(a_1a_2a_{……}a_{4m+4}\)和\(b_1b_2b_{……}b_{4m+1}\)，所以（5）式在实际运算中是不能进行的。
解决办法： 估商，用计算机字长范围内的数字求出的商来代替大整数的商。
估商准备： 1）选取被除数的前两位作为估商的被除数 即 \(a_1a_2a_3a_4\) 和 \(a_5a_6a_7a_8\)
2）选取除数的第一位，作为估商的除数 即\(b_1b_2b_3b_4b_5\)
估商运算：\(zs=[\frac{a_1a_2a_3a_4\times10^4+a_5a_6a_7a_8}{b_1b_2b_3b_4b_5}]\) ----------------------------------（6）
式（6）中的zs是整数商的意思，符号[] 表示向下取整数。计算机很容易求出这个整数商。
估商运算产生的余数：为了后面的证明，我们记估商产生的余数为r_{估}，由(1)、(2)和(6)容易得到：
\(r_{估}= a_1a_2a_3a_4a_5a_6a_7a_8-zs\times b_1b_2b_3b_4b_5\) ------(7)
\(0\leqslant r_{估}<b_1b_2b_3b_4b_5\)----(8)
我们要的结论：
我们的结论是：这个\(zs\)或\(zs-1\)就是我们要找的大整数的商。
结合(5) 式，我们的结论可以写为：\(s_{大整数商}=zs\) 或 \(s_{大整数商}=zs-1\)
证明思路：以\(zs\)为中心，我们可以得到一个大整数的备选商的集合如下：
……\(zs+2\), \(zs+1\),\(zs\),\(zs-1\),\(zs-2\),……
我们只要排除\(zs+1\)及以上的商，排除\(zs-2\)及以下的商，那么剩下的当然就是我们所要的。
证明过程：
反证法第一步：假设大整数的商为\(zs+1\)，记大整数的余数为\(r_{大}\)，那么由式（1），结合（3）和（4）两式，我们有，
\(r_{大}=a_1a_2……a_{4m+4}-(zs+1)\times b_1b_2……b_{4m+1}\)
打开上式中的括号：得
\(r_{大}=a_1a_2……a_{4m+4}-zs\times b_1b_2……b_{4m+1}- b_1b_2……b_{4m+1}\)
拆分上式中的第一项和第二项，有
\(r_{大}= a_1a_2a_3a_4a_5a_6a_7a_8\times10^{4m-4}+a_9a_{10}……a_{4m+4}-zs\times(b_1b_2b_3b_4b_5\times10^{4m-4}+b_6b_7……b_{4m+1})- b_1b_2……b_{4m+1}\)---(9)
继续将(9)式中的第三项乘出来，得到
\(r_{大}= a_1a_2a_3a_4a_5a_6a_7a_8\times10^{4m-4}+a_9a_{10}……a_{4m+4}-zs\times b_1b_2b_3b_4b_5\times10^{4m-4}-zs\times b_6b_7……b_{4m+1}- b_1b_2……b_{4m+1}\)---(10)
注意到（7）式，我们可以把（10）式中的第一项和第三项合并，得
\(r_{大}=r_{估}\times10^{4m-4}+a_9a_{10}……a_{4m+4}-zs\times b_6b_7……b_{4m+1}- b_1b_2……b_{4m+1}\)-----------(11)
现在我们集中精力证明下式
\(r_{大}<0\)-------------------------------------------（12）
为此，我们要分两步进行一些不等式估计
（one）我们先估计\(r_{估}\times10^{4m-4}+a_9a_{10}……a_{4m+4}\)这两项和的最大值。我们有：
\(r_{估}\times10^{4m-4}+a_9a_{10}……a_{4m+4}\leqslant r_{估}\times10^{4m-4}+9…共4m-4个9…<r_{估}\times10^{4m-4}+10^{4m-4}=(r_{估}+1)\times10^{4m-4}\)-----(13)
再由（8）式：得
\(r_{估}<b_1b_2b_3b_4b_5\) --------(14)
因为\(r_{估}\)和\(b_1b_2b_3b_4b_5\)都是非负整数。所以我们可以把(14)式改写如下：
\(r_{估}+1\leqslant b_1b_2b_3b_4b_5\) --------(15)
比较（15）式和（13）式，得到：
\(r_{估}\times10^{4m-4}+a_9a_{10}……a_{4m+4}\leqslant b_1b_2b_3b_4b_5\times10^{4m-4}\)----------(16)
(two)接下来我们要证明下式：
\(b_1b_2……b_{4m+1}>r_{估}\times10^{4m-4}+a_9a_{10}……a_{4m+4}\)-----(17)
实际上，利用（16）式我们有：
\(b_1b_2……b_{4m+1}-(r_{估}\times10^{4m-4}+a_9a_{10}……a_{4m+4})= b_1b_2b_3b_4b_5\times10^{4m-4}+b_6b_7……b_{4m+1}-(r_{估}\times10^{4m-4}+a_9a_{10}……a_{4m+4})> b_1b_2b_3b_4b_5\times10^{4m-4}-b_1b_2b_3b_4b_5\times10^{4m-4}+ b_6b_7……b_{4m+1}\geqslant0\)
因此，（17）成立。
现在我们回到（12）式的证明，实际上我们的证明已经完成：看（11）式中，第一项、第二项和第四项的代数和由（17）式保证是负的。（11）式的第三项也是负值（或者是0）。因此（12）式成立。
因为（12）式与 （2）式矛盾，由反证法的原理，我们得到了大整数的商不能是\(zs+1\)。
同理：我们可证\(zs+2\),……等数都不会是大整数的商。
反证法第一步完成。
反证法第二步：假设大整数的商是\(zs-2\),产生的余数是\(r_{大}\)那么，由（1）、（3）和（4）式，我们有
\(r_{大}=a_1a_2……a_{4m+4}-(zs-2)\times b_1b_2……b_{4m+1}\)
把上式的括号打开：得
\(r_{大}=a_1a_2……a_{4m+4}-zs\times b_1b_2……b_{4m+1}+2b_1b_2……b_{4m+1}\)
再把上式中第一项和第二项拆开：得
\(r_{大}=a_1a_2a_3a_4a_5a_6a_7a_8\times10^{4m-4}+a_9a_{10}……a_{4m+4}-zs\times b_1b_2b_3b_4b_5\times10^{4m-4}-zs\times b_6b_7……b_{4m+1}+2b_1b_2……b_{4m+1}\)----------------------------(18 )
由式（7）我们可以把（18）式中的第一项和第三项求出来，得
\(r_{大}=r_{估}\times10^{4m-4}+a_9a_{10}……a_{4m+4}-zs\times b_6b_7……b_{4m+1}+2b_1b_2……b_{4m+1}\)
为了方便，再把上式中的第四项分解为两项，得
\(r_{大}=r_{估}\times10^{4m-4}+a_9a_{10}……a_{4m+4}-zs\times b_6b_7……b_{4m+1}+b_1b_2……b_{4m+1}+b_1b_2……b_{4m+1}\) --------------------------------（19）
我们将证明：
\(b_1b_2……b_{4m+1}-zs\times b_6b_7……b_{4m+1}>0\)--------------------------(20)
在证明（20）之前，我们要先得到一个估计
\(zs<10000\)-------------------------------------------------------------(21)
如若不然：那么必有 \(zs>=10000\)再由（7）式，得到
\(r_{估}=a_1a_2a_3a_4a_5a_6a_7a_8-zs\times b_1b_2b_3b_4b_5\leqslant a_1a_2a_3a_4a_5a_6a_7a_8-10000\times b_1b_2b_3b_4b_5\leqslant99999999-10000\times10000=-1<0\) (这是因为\(a_1a_2a_3a_4a_5a_6a_7a_8\leqslant99999999\) 而 \(b_1b_2b_3b_4b_5\geqslant10000\) )
显然：这个\(r_{估}<0\)与（2）式矛盾。于是估计式（21）成立。
接下来，我们就来证明（20）式；由于
\(b_1b_2……b_{4m+1}\geqslant10^{4m}\)
\(b_6b_7……b_{4m+1}\leqslant9_{...共4m-4个9...}\)
\(zs<10000\)
所以有：
\(b_1b_2……b_{4m+1}-zs\times b_6b_7……b_{4m+1}>10^{4m}-10000\times9_{——共4m-4个9——}9>10^{4m}-10000\times10^{4m-4}=0\)
即：
\(b_1b_2……b_{4m+1}-zs\times b_6b_7……b_{4m+1}>0\)
这就是我们要证明的（20）式。
现在，我们观察（19）式，它的第一项是一个非负数（有可能为0），而第二项也是非负数，第三项和第四项的代数和由（20）式保证是正的，第五项也是正的。这样我们可以肯定的得到
\(r_{大}>b_1b_2……b_{4m+1}\) -------------------------------------------------（22）
注意到\(b_1b_2……b_{4m+1}\) 就是除数，也就是余数>除数，这就与（2）式矛盾。
由反证法原理，我们知道 \(zs-2\)不能是大整数的商。
同理可证：\(zs-3\)……等数都不会是大整数的商。
现在，我们得到了两个备选商 \(zs\)和 \(zs-1\)，大整数真实的商只能是这二者之一。
最终，我们得到了结论：
在\(10^4\)进制下，除数的第一位采用5位十进制数，使用（6）式估商。那么大整数的第一位商只能是\(zs\)和 \(zs-1\) 二者之一。
更一般地:
在\(10^k\)进制下，除数的第一位采用\(k+1\)位十进制数，参与估商的被除数为\(2k\)位，记估出的商为\(zs\)，那么大整数的第一位商的可能值只能是\(zs\)和 \(zs-1\) 二者之一。
----------------------------------------------------------------------------------------------------------------------------------
理论证明到此结束了，现在谈一点更深入的算法。
为了方便我们记被除数的每一“位”数字为\(a_i\)(i=1，2，……n\)，每一“位” \(a_i\)表示一个\(10^k\)进制的数。
记除数的每一“位”数字为\(b_j\)(j=1，2，……m\)，每一“位” \(b_j\)表示一个\(10^k\)进制的数(\(b_1\)有\(k+1\)位数字)。
除数的第一“位”数字比较特殊，有K+1个数字，专门记为\(B_1\)
好了，现在我们可以把上面的证明结论一一列出：
(A)当求大整数的1“位”商时；
我们选取1“位”除数，2“位”被除数估商。有
\(s_{大整数1位商}=[\frac{a_1a_2a_{......}a_{m+1}}{ B_1b_2b_{……}b_m}]\) 对应 \(s_{估1位商}=[\frac{a_1a_2}{ B_1}]\)----------------------------(23)
(B)当求大整数的2“位”商时；
我们选取2“位”除数，4“位”被除数估商。有
\(s_{大整数2位商}=[\frac{a_1a_2……a_{m+2}}{ B_1b_2b_{……}b_m}]\) 对应 \(s_{估2位商}=[\frac{a_1a_2a_3a_4}{ B_1b_2}]\) ---------------------------------(24)
(C)一般地，当求大整数的s“位”商时；
我们选取s“位”除数，2s“位”被除数估商。有
\(s_{大整数s位商}=[\frac{a_1a_2a_……a_{m+s}}{ B_1b_2b_{……}b_m}]\) 对应 \(s_{估s位商}=[\frac{a_1a_2{......}a _{2s}}{ B_1b_2{......}b_s}]\)-----------------------(25)
第（23）式是我们在上面已证明的结论，当然是正确的。
第(24)和(25)式中，相当于把数的进制扩大了，结论仍然是正确的。
我在本论坛《笔算除法的代码》一文中，就是用的第（23）式做的除法。这个方法的优点是过程简明，层层推进。弱点是商的每一位都要和除数相乘，当除数较大，商的位数也较大时，就相当于做了一个\(O(n^2)\)级的大整数乘法。众所周知，当\(n\)较大时，\(O(n^2)\)级的大整数乘法是很慢的。所以采用（23）式的方法只能用于较小规模的数相除。
当我们采用（25）式来做除法时，由于计算机的字长限制，不能表达（25）式，但是我们可以利用递归来解决，让\(s_{估s位商}=[\frac{a_1a_2a_{……}a _{2s}}{ B_1b_2b_{……}b_s}]\)中的数字每递归一次减少一半。由于（25）式能求出多位商，并且在前期有一半的除数不参与实际运算，在求余数时又可以调用高等级乘法来加速，所以前景看好。但这个方法目前仅仅是设想，还没有写成代码，不知道是不是比（23）式要好些。
为了说明这个（25）式的作用，我们来看一个实际的例子：
例：十万位十进制数\(\div\)七万位十进制数。
因为\(s_{大整的真实商}=[\frac{十万位十进制数}{七万位十进制数}]\)，这个商有约30000位
利用（25）式，我们可以得到：
\(s_{估30000位商}=[\frac{前六万位十进制数}{前三万零一位十进制数}]\)-----------------------(26)
当我们用（23）式（或者其它办法）计算出（26）式中的30000位商时，我们就发现，被除数和除数中竟然共有八万位十进制数没有参与运算。仅仅是在由（1）式最终确定\(s_{大整的真实
商}\)的时候，这八万位数才参与运算，即：
\(r_{大整数的余数}=十万位十进制数-s_{估30000位商}\times七万位十进制数\)---(27)
这时我们可以调用高等级乘法来加速。而且（27）只需运算一次就能确定大整数的商。
完
(C)一般地，当求大整数的s“位”商时；
我们选取s“位”除数，2s“位”被除数估商。有
被除数s+1位就足够了。
需要一次得到多位商时，需要预先求出除数的倒数，估商采用大数乘法来实现。
页:
[1]