代码优化-之-优化除法

《代码优化-之-优化除法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、<<代码优化－之－优化除法>>                                                  HouSisong@GMail.comtag:代码优化,除法,牛顿迭代,减法代替除法,除法优化  说明：文章中的很多数据可能在不同的CPU或不同的系统环境下有不同的结果，数据仅供参考  x86系列的CPU对于位运算、加、减等基本指令都能在1个CPU周期内完成(现在的CPU还能乱序执行，从而使指令的平均CPU周期更小)；现在的CPU,做乘法也是很快的(需要几个CPU周期，每个周期可能启动一个新的乘指令(x87))，但

2、作为基本指令的除法却超出很多人的预料，它是一条很慢的操作，整数和浮点的除法都慢；我测试的英特尔P5赛扬CPU浮点数的除法差不多是37个CPU周期，整数的除法是80个CPU周期，AMD2200+浮点数的除法差不多是21个CPU周期，整数的除法是40个CPU周期。(改变FPU运算精度对于除法无效)(SSE指令集的低路单精度数除法指令DIVPS18个CPU周期,四路单精度数除法指令DIVSS36个CPU周期)  (x86求余运算和除法运算是用同一条CPU指令实现的；据说，很多CPU的整数除法都是用数学协处理器的浮点除法器完成的；有一个推论就是，浮点

3、除法和整数除法不能并行执行.  (ps:intel的p4imul指令可能有14周期(或15-18)的延迟才能得到结果) 本文将给出一些除法的优化方法或替代算法 (警告:某些替代算法并不能保证完全等价!) 1.尽量少用除法  比如：if(x/y>z)...  改成：if(((y>0)&&(x>y*z))

4、

5、((y<0)&&(x=count)index=index%count; //assert(index

6、>=count)index=index-count; 2.用减法代替除法  如果知道被除数是除数的很小的倍数，那么可以用减法来代替除法  比如： uint32x=200;       uint32y=70;          uint32z=x/y;  改成： uintz=0;          while(x>=y)          {             x-=y; ++z;          }  一个用减法和移位完成的除法(如果你没有除法指令可用:)    uint32div(uint64u,uint32z)//returnu

7、/z       {        uint32x=(uint32)(u>>32);        uint32y=(uint32)u;        //y保存商x保存余数        for(inti=0;i<32;++i)        {            uint32t=((int32)x)>>31;             x=(x<<1)

8、(y>>31);            y=y<<1;            if((x

9、t)>=z)            {                x-=z;        

10、        ++y;            }        }        returny;    }    (该函数经过了测试；z==0需要自己处理；对于有符号除法，可以用取绝对值的方法(当然也不是轻松就能写出完全等价的有符号除法的:)；如果不需s的64bit长度，仅需要32bit,那么可以化简这个函数，但改进不多)    3.用移位代替除法 (很多编译器能自动做好这个优化)  要求除数是2的次方的常量；(同理：对于某些应用，可以优先选取这样的数来做除数)  比如： uint32x=213432575;       uint32y

11、=x/8;  改成： y=x>>3;  对于有符号的整数；  比如： int32x=213432575;       int32y=x/8;  改成： if(x>=0) y=x>>3;            else y=(x+(1<<3-1))>>3; 4.合并除法  (替代方法不等价，很多编译器都不会帮你做这种优化)  适用于不能用其它方法避免除法的时候；  比如： doublex=a/b/c;  改成： doublex=a/(b*c);  比如： doublex=a/b+c/b;  改成： doublex=(a+c)/b;  比如： 

12、doublex=a/b;   doubley=c/d;   doublez=e/f;  改成： doubletmp=1.0/(b*d*f);          do