曲径通幽论坛

标题: 提高整数除法的精度 [打印本页]

作者: beyes 时间: 2011-4-2 18:15
标题: 提高整数除法的精度
一般的整除，比如 115 ÷ 31 ，直接得出的结果是：

115 / 31 == 3

考虑 115 ÷ 31 的余数，那么可以看到余数为 22：

115 % 31 == 22

因为 22 已经比较接近 31，这时我们可能更希望结果等于 4 ，而不是等于 3，所以调整除法表达式，获得更准确的值：

(115 + (115%31)/2) / 31

上面，我们利用余数进行结果的四舍五入进行调整，提高了运算精度。

比较下面的代码：

[C++] 纯文本查看 复制代码

#include <stdio.h>





#define SH_DIV(NOM,DEN,LSH) (   (((NOM) / (DEN)) << (LSH))              \

                + ((((NOM) % (DEN)) << (LSH)) + (DEN) / 2) / (DEN))





#define SH_DIV2(NOM,DEN) ( (NOM) / (DEN) + (((NOM) % (DEN) + (DEN) / 2)) / (DEN) )





int main()

{

        printf ("%d\n", SH_DIV(1000,  SH_DIV(115,31,8), 8));





        printf ("%d\n", SH_DIV2(1000, SH_DIV2(115, 31)));





        return (0);

}

运行输出：

$ ./temp
269
250

对于输出结果，可以利用计算器验证一下(计算器的结果为：269.56521739130434782608695652174)，可见第一个结果比第二种结果更为精确。

上面程序中，SH_DIV 宏对商和余数都左移 8 位进行了扩展，SH_DIV(115,31,8) 获得的是一个中间结果(经过 256 倍的扩展)，那么 SH_DIV(1000, SH_DIV(115,31,8), 8) 则是相当于将 1000 ÷ SH_DIV(115,31,8) 得到的商再乘以 256 ，从而还原出了最终结果。总的概括的来说，就是 1000 先除以一个扩大了 256 倍的数，然后再乘以 256 ，其结果不变。其本质思想是，扩展后，原本在扩展前要丢掉的小数部分被扩展后包含了进来了，这样就进一步提高了精确度。

SH_DIV 宏来自 linux 内核源代码 include/linux/jiffies.h 。

欢迎光临曲径通幽论坛 (http://www.groad.net/bbs/)