04 2014
26

用整数运算替代浮点运算
2014年04月26日

我们做软件,尤其是编写计算密度低的程序,通常无需最优化运算效率,一般觉得差不多即可。 然而有的软件需求对运算速度非常重视,比如游戏、大量数据计算、批量媒体文件处理等,在一些处理能力较差的设备上也需要特别注意优化运算效率。 如果不考虑运算效率,游戏没什么惊艳特效也会卡,批量计算持续几天都算不完。 通常来说,改进算法的时间复杂度是对效率提升最为显著的办法,但如果遇到算法已经很难优化的时候,想要进一步提高效率就要在一些细节上下工夫了。 比如能用为运算的时候,绝不用乘法或除法,还有就是,尽可能用整数运算而不用浮点运算。

当然用整数替代浮点并不一定会提高性能,现如今FPU(浮点运算单元)算是CPU中的标配,而在有FPU的设备上浮点运算并不比整数运算慢,所以并不必要过分追求用整数替代浮点。 然而在一些小型嵌入式设备、低端配置手机上、型号较老的服务器上可能并不配备FPU或者FPU浮点能力较差,在这种情况下用整数替代浮点会显著提高效率。 因为用软件的方式完全模拟IEEE标准的浮点运算,会较慢。

所谓用整数运算替代浮点运算无非就是把一个整数,按照需要划分成两部分,一部分为整数部分余下为小数部分。 用例子说明就是用1500来代替1.5,整数最小的三位表示小数点后面的部分,这样1.5+1.5=3.0就变成了1500+1500=3000,乘法与除法则要稍微注意,1.5×1.5=2.25是1500×1500/1000=2250。 然而用10、100、1000作为小数划分并不是最好的选择,因为位运算比乘法、除法快很多,所以64、128、256、512等是更好的选择。 比如以512为划分的基数,则1.5用768表示(1.5×512=768),1.5×1.5=2.25就变为768×768»9=1152(2.25×512=1152)。 最终必要的时候重新转换成浮点或者只取整,只要处以基数即可。

这种方式计算比完全的IEEE浮点运算要简单的多,所以处理速度也更快,但是当然,可表达的数值精度、宽度等都比较有限,但是在很多情况下这就足够了。 不过这里要特别提的是,如果使用GCC编译(包括Linux、Unix、Darwin、Android NDK、iOS等平台下的GCC)可以通过添加-ffast-math来加速浮点运算。 其加速原理也是使用非完整的IEEE浮点标准进行运算并且舍弃掉了许多容错、线程安全等方面的能力,要根据情况谨慎使用,不过通常来说用来做游戏的图像渲染等这个精度完全足够。