[代码优化-之-优化除法.docxVIP

代码优化－之－优化除法?HouSisong@GMtag:代码优化,除法,牛顿迭代,减法代替除法,除法优化 说明：文章中的很多数据可能在不同的CPU或不同的系统环境下有不同的结果，数据仅供参考 x86系列的CPU对于位运算、加、减等基本指令都能在1个CPU周期内完成(现在的CPU还能乱序执行，从而使指令的平均CPU周期更小)；现在的CPU,做乘法也是很快的(需要几个CPU周期，每个周期可能启动一个新的乘指令(x87))，但作为基本指令的除法却超出很多人的预料，它是一条很慢的操作，整数和浮点的除法都慢；我测试的英特尔P5赛扬CPU浮点数的除法差不多是37个CPU周期，整数的除法是80个CPU周期，AMD2200+浮点数的除法差不多是21个CPU周期，整数的除法是40个CPU周期。(改变FPU运算精度对于除法无效) (SSE指令集的低路单精度数除法指令DIVPS 18个CPU周期,四路单精度数除法指令DIVSS 36个CPU周期)?? (x86求余运算和除法运算是用同一条CPU指令实现的； 据说，很多CPU的整数除法都是用数学协处理器的浮点除法器完成的；有一个推论就是，浮点除法和整数除法不能并行执行.??(ps:intel的p4 imul指令可能有14周期(或15-18)的延迟才能得到结果) 本文将给出一些除法的优化方法或替代算法 (警告:某些替代算法并不能保证完全等价!) 1.尽量少用除法 比如： if (x/yz) ... 改成： if ( ((y0)(xy*z))||((y0)(xy*z)) ) ... (少用求余) 比如： ++index; if (index=count) index=index % count;? //assert(indexcount*2); 改成： ++index; if (index=count) index=index - count; 2.用减法代替除法 如果知道被除数是除数的很小的倍数，那么可以用减法来代替除法 比如： uint32 x=200; uint32 y=70; uint32 z=x/y; 改成： uint z=0; while (x=y) { x-=y;? ++z; } 一个用减法和移位完成的除法 (如果你没有除法指令可用:) uint32 div(uint64 u,uint32 z) //return u/z??? { uint32 x=(uint32)(u32); uint32 y=(uint32)u; //y保存商 x保存余数 for (int i=0;i32;++i) { uint32 t=((int32)x) 31;? x=(x1)|(y31); y=y1; if ((x|t)=z) { x-=z; ++y; } } return y; } (该函数经过了测试；z==0需要自己处理；对于有符号除法，可以用取绝对值的方法(当然也不是轻松就能写出完全等价的有符号除法的:)； 如果不需s的64bit长度，仅需要32bit,那么可以化简这个函数，但改进不多)?? 3.用移位代替除法 (很多编译器能自动做好这个优化) 要求除数是2的次方的常量； (同理：对于某些应用，可以优先选取这样的数来做除数) 比如： uint32 x=213432575; uint32 y=x/8; 改成： y=x3; 对于有符号的整数； 比如： int32 x=213432575; int32 y=x/8; 改成： if (x=0)? y=x3;?? else? y=(x+(13-1))3; 4.合并除法 (替代方法不等价，很多编译器都不会帮你做这种优化) 适用于不能用其它方法避免除法的时候； 比如： double x=a/b/c; 改成： double x=a/(b*c); 比如： double x=a/b+c/b; 改成： double x=(a+c)/b; 比如： double x=a/b; double y=c/d; double z=e/f; 改成： double tmp=1.0/(b*d*f); double x=a*tmp*d*f; double y=c*tmp*b*f; double z=e*tmp*b*d;??? 5.把除法占用的时间充分利用起来? CPU在做除法的时候，可以不用等待该结果(也就是后面插入的指令不使用该除法结果)，而插入多条简单整数指令(不包含整数除法，而且结果不能是一个全局或外部变量等)，把除法占用的时间节约出来；? (当除法不可避免的时候，这个方法很有用) 6.用查表的方法代替除法 （适用于除数和被除数的可能的取值范围较小的情况，否则空间消耗太大） 比如 uint8? x;? uint8 y;? uint8? z=x/y; 改成 uint8? z=table[