我有一個以高頻運行的控制迴路，需要計算每個週期的平方根。典型的平方根函數工作正常，但花費時間過長。由於我在每個週期中取平方根的值不會變化太多，因此我想找到一個迭代平方根，它將收斂並跟蹤正確的結果。這樣我可以在每個時間步驟做一次迭代，而不是很多次。跟蹤移動值的平方根
問題是我看到的所有迭代平方根方法在輸入發生變化時可能會失敗。特別是當輸入變爲零然後又增加時，看起來會有問題 - 方法不喜歡以猜測零開始。
我的輸入範圍是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