math - 跟踪移动值的平方根

Question

我有一个高频运行的控制回路，需要在每个周期计算一个平方根。典型的平方根函数可以正常工作，但会花费过多的时间。由于我取平方根的值在每个循环中变化不大，我想找到一个迭代平方根，它会收敛，然后跟踪正确的结果。这样我可以在每个时间步进行一次迭代，而不是多次。

问题是当输入发生变化时，我见过的所有迭代平方根方法都可能会失败。特别是当输入变为零然后再次增加时，看起来会有问题——这些方法不喜欢从猜测零开始。

我的输入范围是 0-4.5，我需要大约 0.01 的精度，因此使用 0.01 的增量/减量可能需要很长时间 - 我希望它大部分在 10 个周期或更短的时间内收敛。

仅供参考，我使用的是 16/32 位定点，输入是 16 位 q12。它在微控制器上，所以我对使用 1K 查找表不感兴趣。代码也是从 simulink 模型生成的，它们的查表功能相当多的开销。

有一个很好的解决方案吗？

score 5 · Accepted Answer

0-4.5 的范围相当小。精度为 0.01，这只有 450 次可能的计算。您可以在编译时将它们全部计算为常量，并在运行时进行查找。

score 2 · Accepted Answer

如果您提前知道要处理的范围，我建议您使用查找表。生成一个数组或哈希表（取决于您使用的语言）到您需要的精度级别，并在需要您的根时参考它。

score 2 · Accepted Answer

我尝试了二阶泰勒展开sqrt(x)并得到以下结果

如果y=sqrt(x)你y_c = sqrt(x_c)已经知道了：

t = x-3*x_c;
y = (12*x_c*x_c-t*t)/(8*y_c*y_c*y_c);

越大x近似越好。在最坏的情况下，x_c=0.01结果x=0.02与0.1375实际结果相比，sqrt(0.02)=0.1414或者其差异0.0039为 under 0.01。

我测试了代码C#并看到了稳定的33%加速与Math.Sqrt().

score 1 · Accepted Answer

您可以使用一杆哈雷方法。它具有三次收敛性，因此如果值略有移动，则应该非常精确：

x_{n+1} = x_n * (x_n^2 + 3Q) / (3 x_n^2 + Q)

这三次收敛到sqrt(Q)。

4 回答 4