大整数除法之最优估商的理论证明

只是呼吸

作为除法中的一种-----估商法，有一定的实际应用，尤其在数字规模不太大的时候是比较有效率的。
本文将在一个特殊的数据结构下，给出估商的最优解。

理论基础： 被除数=商\(\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）只需运算一次就能确定大整数的商。


  完


  
         
     
         
         
         

liangbch

(C)一般地，当求大整数的s“位”商时；
             我们选取s“位”除数，2s“位”被除数估商。有

被除数s+1位就足够了。
需要一次得到多位商时，需要预先求出除数的倒数，估商采用大数乘法来实现。