我有一个以高频运行的控制回路，需要计算每个周期的平方根。典型的平方根函数工作正常，但花费时间过长。由于我在每个周期中取平方根的值不会变化太多，因此我想找到一个迭代平方根，它将收敛并跟踪正确的结果。这样我可以在每个时间步骤做一次迭代，而不是很多次。跟踪移动值的平方根
问题是我看到的所有迭代平方根方法在输入发生变化时可能会失败。特别是当输入变为零然后又增加时，看起来会有问题 - 方法不喜欢以猜测零开始。
我的输入范围是0-4.5，我需要大约0.01的精度，所以使用0.01的递增/递减可能需要很长时间 - 我希望它主要收敛在10个周期或更少。
仅供参考我使用16/32位定点输入是16位q12。这是在一个微控制器上，所以我不想使用1K查找表。该代码也是从simulink模型生成的，它们的表查找函数充满了开销。
有没有一个很好的解决方案呢？
您可以使用哈雷法的一个镜头。它具有收敛立方米，因此，如果该值轻微移动应该是相当准确：
x_{n+1} = x_n * (x_n^2 + 3Q)/(3 x_n^2 + Q)
这cubcially收敛到sqrt(Q)。
参考：http://www.mathpath.org/Algor/squareroot/algor.square.root.halley.htm哈雷彗星的方法
我的模拟显示这是最好的。这也是我尝试过的唯一合理的工作，接近于零。至少在反馈中x_n需要被剪切到一个很小的值，以防止被零除。 – phkahler 2012-04-27 14:30:40
如果这是浮点数，则可以将输入的指数减半，并使用结果值作为第一个估计值，以便将该值或任何其他迭代平方根算法应用到该算法中。 – 2012-05-21 19:50:00
@R ..初始猜测是最后更新的值（请参阅问题）。但是，是的，在一个更通用的环境中，这会很好地工作。 – 2012-05-21 20:11:35
范围0-4.5相当小。精度为0.01，那只有450个可能的计算。您可以在编译时将它们全部计算为常量，并在运行时进行查找。
太多内存 - 编辑问题以反映这一点。 – phkahler 2012-04-12 15:15:39
你有没有尝试过发布这个问题或类似的数学堆栈交换网站？ – 2012-04-12 15:22:04
我建议你使用查找表，如果你知道在高级你正在处理的范围。生成一个数组或哈希表（取决于您所使用的语言）达到您需要的精度级别，并在需要根源时引用此表。
我试过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.01之下。
我用C#测试了代码，看到了稳定的33%加速比Math.Sqrt()。
一杆（http://www.mathpath.org/Algor/squareroot/algor.square.root.halley.htm）应该做的罚款。如果你想避免分裂，改为更新1/sqrt（x）并使用牛顿或哈雷。 – 2012-04-12 15:58:39
你是什么意思，价值变化？你是说你想找到'sqrt（x + epsilon）'知道'x'和'sqrt（x）'而不必直接计算它？或者你说包含x的寄存器是不稳定的，并且可以在计算过程中改变（！？！）？ – 2012-04-12 20:50:49
看看游戏中使用的'FastSqrt'功能http://www.gamedev.net/topic/278840-fast-sqrt/ – ja72 2012-04-13 19:31:59