估计平方根

Question

我正在编写一个iPhone应用程序，该应用需要计算每秒1/30次约2000次的平方根。 SQRT（）在计算机上工作正常，但是帧速率在iPhone或iPad上的10 fps下降到约10 fps，我已经优化了其余代码。我听说可以通过估计平方根来大幅度加速，但是我找不到任何代码可以做到这一点。我只需要一个或两个小数的精度。关于如何执行此操作的任何建议，或其他加快速度的方法。

谢谢！

Answer 1

您希望您的估计值如何？如果您知道您希望自己的估计与真实的SQRT有多近 牛顿的方法 是你的朋友。

您知道传递给SQRT的值范围吗？如果是这样，您可以组成一张在启动时预先计算的查找表（甚至是从启动时从磁盘上读取的，具体取决于结果更快的速度）。找到桌子中最接近输入的最接近的内容，然后获得估计。

Answer 2

除非您实际上 需要 平方根，比较平方值而不是原始值和平方根。

如果您只需要比较，那么平方比取平方根要快得多（并且更准确）。这是大多数游戏的做法。

Answer 3

您知道要找到的平方根的值范围吗？假设您的值范围从0到10。然后您可以预先计算一个数组：

sqrt_val[0] = 0;
sqrt_val[1] = 1;
sqrt_val[2] = // the sqrt of 2
...
sqrt_val[10] = // the sqrt of 10

然后，在运行时，您将所需的SQRT的数字转换为整数（例如3.123变为3），然后将其用作索引（3）来查找预计值。

当然，如果您想要更好的分辨率，则可以增加数组中的项目数量。

Answer 4

首先，您确定平方根实际上是瓶颈吗？你介绍了吗？实际上，即使在手机上，每一秒钟的每1/30颗根实际上并不多，也不是很多。手臂文档引用了单精度方形根和60个循环的33个循环； 600MHz处理器可以做 千万 平方根每秒（如果说明完全是管道的，则更多）。

如果您已经进行了介绍，而Square Root确实是瓶颈，则需要使用霓虹灯 vrsqrte.f32 操作说明。该指令非常快，可以同时为您提供四个浮点数的近似正方形根。然后您可以使用 vmul.f32 获得近似平方根的指令（尽管对于许多用途而言，倒数比平方根本身更有用）。

Answer 5

也许这是给你的：
快速平方根
如果此方法没有提供准确性，则还需要大量其他迭代方法，您可以在速度和准确性之间选择或多或少的精确度：
计算平方根的方法

Answer 6

您可以在iPhone上做出的最简单更改是使用SQRTF（）而不是SQRT（）。单精度浮点数学比双重精度快得多，尤其是在3GS复古和更新的设备上。

Answer 7

如果您需要平方根来计算毕达哥拉斯三角形（sqrt（x*x + y*y）），并且x和y都是无效的，那么与之相关的近似值非常快

max(x,y) + min(x,y)*0.333

最大误差为5.7％。请注意min（）和max（）中的分支错误预测。

Answer 8

快速的Google搜索出现了各种链接。

http://en.wikipedia.org/wiki/methods_of_computing_square_square_ roots#approximations_that_dat_deption_on_ieee_representation

http://www.azillionmonkeys.com/qed/sqroot.html

Answer 9

如果您具有“正常”的正浮子或双倍，而不是int，并且想使用表格查找方法，则可以进行两个单独的桌子查找，一个用于指数（重新偏见），一个用于几个位的Mantissa（移位和掩盖比特菲尔德提取），然后将两个表乘以查找结果。