平方根倒数快速算法

问题

想快速计算某数的平方根倒数。

解决方案

在QuakeⅢ Arena的源代码中，这个奇怪的算法对一个幻数进行整数运算，来计算平方根倒数的浮点近似值。

在CoffeeScript中，他使用经典原始的变量，以及由Chris Lomont发现的新的最优32位幻数。除此之外，还使用64位大小的幻数。

另一特征是可以通过控制牛顿迭代法的迭代次数来改变其精确度。

相比于传统的，该算法在性能上更胜一筹，这归功于使用的机器及其精确度。

运行的时候使用coffee -c script.coffee来编译script：

然后复制粘贴编译的JS代码到浏览器的JavaScript控制台。

注意：需要一个支持类型数组的浏览器

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

fastInvSqrt_typed = (n, precision=1) ->
    # 使用类型数组。现在只能在浏览器中操作。
    # 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]

单次运行示例

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