除法快速计算

原文地址： http://blog.sina.com.cn/s/blog_6ce18c380100nqhw.html

        今天在水木circuit板看到一个问题：如何计算 X/60 ，结果精度要求8-bit。

 

        对计算机来说，算除法太困难了。不过如果被除数是固定的，就可以设计快速计算程序：把除法凑成一系列 X/(2^n) 之和。

 

        X/60，我的方法是这样的:

 

    如果计算结果是8bit的数字量，我们有以下结论：

             1. X最大可能的值是 255*60

             2. 结果的截断误差在±1/2以内

 

    如果当X为255*60时(最糟糕状况)，我们的计算误差仍然小于±1/2,算法的精度就是合格的。

 

    设计算误差为Δ(数量比)，为了达到精度，应该有：

                      255×60×Δ < 1/2

                 即：Δ 至少要小于 1/(255×60×2)

    我们把计算精度进一步提高，取Δ＝1/(2^16)  [=1/(256×64×2)]。

 

    显然有等式：

                  X(1/60 - Δ)    <   X/60 <  X(1/60 + Δ)

 

     推导之：

       <=>   1/60 - 1/(2^16)  <  1/60  <  1/60 + 1/(2^16)

       <=>   (2^14 - 15)/(15*2^16)  <  1/60  <  (2^14 + 15)/(15*2^16)

       <=>   (16384 - 15)/(15*2^16) 

                         <  1/60 = 16384/(15*2^16) 

                                     <  (16384 + 15)/(15*2^16)

 

    我们在 16384±15之间(精度要求范围之内)寻找一个可以被15整除，而且最接近16384的数，它就是： 16380，靠它来把分母上的15约掉。

 

    于是有 1/60 ≈ 16380/(15*2^16) = 1092/2^16， 误差为 4/(15*2^16) 小于1/(2^17)。

 

    1092/(2^16) = (1024+64+4)/(2^16)

                       = 1/(2^6) + 1/(2^10) + 1/(2^14)

 

    故而：

           X/60 ≈ X/(2^6) + X/(2^10) + X/(2^14)  (计算误差小于 8bit数的截断误差)，至此，如何用程序快速计算X/60，已经显而易见了。

 

        规范得推导下来似乎很麻烦，其实思路没这么复杂，很简单的，其实本质就是把1/60转换成二进制数，计算深度能满足误差要求即可，数里的每个1将对应到一个求和项，

        用这种方法，得到的只有 X/(2^n)的求和式，如果考虑即可以加X/(2^n)，也可以减X/(2^n)，项数还可以更少。