Fast Inverse Square Root 演算法…

中文稱為「平方根倒數速演算法」,英文則是「Fast Inverse Square Root」。

好像是在 Twitter 還是 Facebook 上看到的 (還是是在其他管道?),仔細看中文版維基百科條目,發現中文版的資料相當完整了 (看了一下歷史記錄,是去年 2012 年 6 月的時候從英文版翻出來的)。

當時很有名的 magic hack,比查表法快:

在1990年代初(也即該演算法發明的大概時間),軟體開發時通用的平方根計算方法多是從尋找表中取得近似值,而這段代碼取近似值耗時比之更短,達到精確度要求的速度也比通常使用的浮點除法計演算法快四倍,

然後還比 CPU 指令集快 XD

由於演算法所生成的用於輸入牛頓法的首次近似值已經相當精確,此演算法所得近似值的精度已可接受,而若使用與《雷神之鎚III競技場》同為1999年發行的Pentium III中的SSE指令rsqrtss計算,則計算平方根倒數的收斂速度更慢,精度也更低。

Update:請參考 comment,看起來中文版有誤譯…

我本來以為我之前寫過,找了找沒翻到… 補記錄下來 :p

Related Posts:

This entry was posted in Computer, Game, Murmuring, Programming, Recreation, Software and tagged , , , , , , , , , , . Bookmark the permalink.
  • Ying-Chieh Liao
  • scw

    中文版 wikipedia 翻譯這個演算法和 SSE 的比較似乎翻錯的; 英文版 wikipedia 和參考的文章 http://assemblyrequired.crashworks.org/2009/10/16/timing-square-root/ 結論都是 rsqrtss 比較精確也比較快. (however, it is much slower and less accurate than using the SSE instruction rsqrtss on x86 processors, and also released in 1999. 那個 and 很奇怪, 應該是 which 比較順).

  • http://blog.gslin.org/ Gea-Suan Lin

    感謝… 先劃掉了 :o

  • http://blog.gslin.org/ Gea-Suan Lin

    我知道你寫過,不過我以為我寫過… @_@