学步园

今年年初搞手机游戏时搞的小研究，现在从自己的私人blog中丢出来。

日期：2009-02-03

终于搞定：8位定点数开方程序

靠，这两天卡在这好久，不知是因为过年了人松懈了脑子转不快了还是咋的，本来以为这东西很简单，结果n天没搞定，后来一想就烦就直接去打游戏去了。不过回头来还得搞，最后对比了几种方法，参考了几段别人的代码，自己又推导了n久（主要时间都花在优化上：如何改用更快的运算方式而又保证结果正确？）之后完成了下面的程序：

适用于8位定点正数，这样以来我之前写的那个8位定点数学类就又可以完善了。

int Sqrt8(int a)<br /> {<br /> int i,c;<br /> int b = 0;<br /> if(a<=0x1000)<br /> {<br /> a<<=8;<br /> for(i = 0x40000000; i !=0; i >>= 2)<br /> {<br /> c = i + b;<br /> b >>= 1;<br /> if(c <= a)<br /> {<br /> a -= c;<br /> b += i;<br /> }<br /> }<br /> return b;<br /> }else<br /> {<br /> for(i = 0x40000000; i > 0x10; i >>= 2)<br /> {<br /> c = i + b;<br /> b >>= 1;<br /> if(c <= a)<br /> {<br /> a -= c;<br /> b += i;<br /> }<br /> }<br /> b<<=8;<br /> for(i=0x1000;i!=0;i>>=2)<br /> {<br /> c = (i + b)>>8;<br /> b >>= 1;<br /> if(c <= a)<br /> {<br /> a -= c;<br /> b += i;<br /> }<br /> }<br /> return b;<br /> }<br /> }

因为是逼近计算的，可以保证最高的精度（8位定点数能表示的极限）。至于速度并不像有些人想象的那么慢，实际上此代码经过充分的优化，循环次数最多为20次，所有操作数均为32位整数，计算均用加减和移位来处理，没有用到乘法更没有用到除法，速度也不会太慢。

没有采用查表法，因为综合考虑之后觉得查表法不见得会更好：要么表得足够大，这样会比较占用内存，要么就要损失精度，如果不想损失精度的话就得加入调整代码对查表的结果进行调整，这样的话速度也会慢下来。特别是针对手机等移动平台的ARM处理器，查一个大表恐怕比执行几十条指令更慢（要访内、还要重新填充缓存），在加上调整代码中的除法，估计速度不会快多少。

（补充：抽时间在我的dopod577W上测试了下，用JMM和JBED两个模拟器上测试的结果均是查表法不仅没有快多少，反倒比上述代码慢一倍以上，看来经过我多次优化的这个开方程序效率还是不错地～）