## 問題 你想[快速](http://en.wikipedia.org/wiki/Fast_inverse_square_root "http://en.wikipedia.org/wiki/Fast_inverse_square_root")的計算一個數字的逆平方根。 ## 方法 根據 Quake III Arena?[源代碼](ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip "ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip"), 這種奇怪的算法使用整數運算，以及一個‘神奇的數字(幻數)’來計算逆平方根的近似值。 在此CoffeeScript的變種中，我不僅提供原始的經典之作，還有由[Chris Lomont](http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf "http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf")發現的新最佳的32位幻數,此外還有64位大小的幻數。 包含的另一個特征是能夠改變的精度水平。 這是通過控制執行[牛頓法](http://en.wikipedia.org/wiki/Newton%27s_method "http://en.wikipedia.org/wiki/Newton%27s_method")的迭代次數實現。 這個算法在經典的解法上仍然可以提升性能，這取決于計算機和精確水平。 用coffee編譯運行這段腳本： coffee -c script.coffee 然后復制粘貼編譯后的js代碼到你的瀏覽器JavaScript控制臺中。 提示：你需要一個瀏覽器支持?[類型化數組](https://developer.mozilla.org/en/JavaScript_typed_arrays "https://developer.mozilla.org/en/JavaScript_typed_arrays")。 參考: 1. [ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip](ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip) 2. [http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf](http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf) 3. [http://en.wikipedia.org/wiki/Newton%27s_method](http://en.wikipedia.org/wiki/Newton%27s_method) 4. [https://developer.mozilla.org/en/JavaScript_typed_arrays](https://developer.mozilla.org/en/JavaScript_typed_arrays) 5. [http://en.wikipedia.org/wiki/Fast_inverse_square_root](http://en.wikipedia.org/wiki/Fast_inverse_square_root) 源代碼來源于gist:?[https://gist.github.com/1036533](https://gist.github.com/1036533) ~~~ ### Author: Jason Giedymin <jasong _a_t_ apache -dot- org> http://www.jasongiedymin.com https://github.com/JasonGiedymin Appearing in the Quake III Arena source code[1], this strange algorithm uses integer operations along with a 'magic number' to calculate floating point approximation values of inverse square roots[5]. In this CoffeeScript variant I supply the original classic, and newer optimal 32 bit magic numbers found by Chris Lomont[2]. Also supplied is the 64-bit sized magic number. Another feature included is the ability to alter the level of precision. This is done by controling the number of iterations for performing Newton's method[3]. Depending on the machine and level of percision this algorithm may still provide performance increases over the classic. To run this, compile the script with coffee: coffee -c <this script>.coffee Then copy & paste the compiled js code in to the JavaSript console of your browser. Note: You will need a browser which supports typed-arrays[4]. References: [1] ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip [2] http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf [3] http://en.wikipedia.org/wiki/Newton%27s_method [4] https://developer.mozilla.org/en/JavaScript_typed_arrays [5] http://en.wikipedia.org/wiki/Fast_inverse_square_root ### approx_const_quake_32 = 0x5f3759df # See [1] approx_const_32 = 0x5f375a86 # See [2] approx_const_64 = 0x5fe6eb50c7aa19f9 # See [2] fastInvSqrt_typed = (n, precision=1) -> # Using typed arrays. Right now only works in browsers. # Node.JS version coming soon. y = new Float32Array(1) i = new Int32Array(y.buffer) y[0] = n i[0] = 0x5f375a86 - (i[0] >> 1) for iter in [1...precision] y[0] = y[0] * (1.5 - ((n * 0.5) * y[0] * y[0])) return y[0] ### Sample single runs ### testSingle = () -> example_n = 10 console.log("Fast InvSqrt of 10, precision 1: #{fastInvSqrt_typed(example_n)}") console.log("Fast InvSqrt of 10, precision 5: #{fastInvSqrt_typed(example_n, 5)}") console.log("Fast InvSqrt of 10, precision 10: #{fastInvSqrt_typed(example_n, 10)}") console.log("Fast InvSqrt of 10, precision 20: #{fastInvSqrt_typed(example_n, 20)}") console.log("Classic of 10: #{1.0 / Math.sqrt(example_n)}") testSingle() ~~~ ## 討論 有問題嗎？