CoffeeScript 平方根倒數(shù)快速算法

平方根倒數(shù)快速算法

問題

你想快速計(jì)算某數(shù)的平方根倒數(shù)。

解決方案

在QuakeⅢ Arena的源代碼中，這個(gè)奇怪的算法對一個(gè)幻數(shù)進(jìn)行整數(shù)運(yùn)算，來計(jì)算平方根倒數(shù)的浮點(diǎn)近似值。

在CoffeeScript中，他使用經(jīng)典原始的變量，以及由Chris Lomont發(fā)現(xiàn)的新的最優(yōu)32位幻數(shù)。除此之外，還使用64位大小的幻數(shù)。

另一特征是可以通過控制牛頓迭代法的迭代次數(shù)來改變其精確度。

相比于傳統(tǒng)的，該算法在性能上更勝一籌，這歸功于使用的機(jī)器及其精確度。

運(yùn)行的時(shí)候使用coffee -c script.coffee來編譯script：

然后復(fù)制粘貼編譯的JS代碼到瀏覽器的JavaScript控制臺。

注意：你需要一個(gè)支持類型數(shù)組的瀏覽器

參考：

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/JavaScripttypedarrays
5. http://en.wikipedia.org/wiki/Fastinversesquare_root

以下的代碼來源于：https://gist.github.com/1036533

###

Author: Jason Giedymin <jasong _a_t_ apache -dot- org>
        http://www.jasongiedymin.com
        https://github.com/JasonGiedymin

在 Quake Ⅲ Arena 的源代碼 [1](ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip) 中，這個(gè)奇怪的算法對一個(gè)幻數(shù)進(jìn)行整數(shù)運(yùn)算，來計(jì)算平方根倒數(shù)的浮點(diǎn)近似值 [5](http://en.wikipedia.org/wiki/Fast_inverse_square_root)。

在 CoffeeScript 中，我使用經(jīng)典原始的變量，以及由 Chris Lomont [2](http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf) 發(fā)現(xiàn)的新的最優(yōu) 32 位幻數(shù)。除此之外，還使用 64 位大小的幻數(shù)。

另一特征是可以通過控制牛頓迭代法 [3](http://en.wikipedia.org/wiki/Newton%27s_method) 的迭代次數(shù)來改變其精確度。

相比于傳統(tǒng)的，該算法在性能上更勝一籌，歸功于使用的機(jī)器及其精確度。

運(yùn)行的時(shí)候使用 coffee -c script.coffee 來編譯 script： 

然后復(fù)制粘貼編譯的 JS 代碼到瀏覽器的 JavaScript 控制臺。

注意：你需要一個(gè)支持類型數(shù)組 [4](https://developer.mozilla.org/en/JavaScript_typed_arrays) 的瀏覽器

###

approx_const_quake_32 = 0x5f3759df # See [1]
approx_const_32 = 0x5f375a86 # See [2]
approx_const_64 = 0x5fe6eb50c7aa19f9 # See [2]

fastInvSqrt_typed = (n, precision=1) ->
    # 使用類型數(shù)組?，F(xiàn)在只能在瀏覽器中操作。
    # Node.JS 的版本即將推出。

    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]

### 單次運(yùn)行示例

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()