CoffeeScript Javascript Fast Inverse Square with Typed Arrays

fast_inv_square.coffee

###

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

This looks like a nice exercise but running the code resulted in a much slower function i tried it in

• Firefox 27.0.1
  • 1 Million fast inverse sqrt = 4 seconds
  • 1 Million inverse sqrt = half a second
• Chrome 33.0.1750.152
  • 1 Million fast inverse sqrt = 2.5 seconds
  • 1 Million inverse sqrt = 1 second

More iterations don't affect much the performance so i think the bottleneck is instantiation of the Arrays.
Nonetheless here is a performance boost by instantiating the arrays outside the function, caching n2 = n * 0.5, y2 = y[0] and using by 1 in the for loop. (by the way the original code runs at least one newton iteration so i changed the range to [0...precision])

y = new Float32Array(1)
i = new Int32Array(y.buffer)
fastInvSqrt_typed = (n, precision = 1) ->
  y[0] = n
  i[0] = 0x5f375a86 - (i[0] >> 1)

  n2 = n * 0.5
  y2 = y[0]
  for iter in [0...precision] by 1
    y2 = y2 * (1.5 - (n2 * y2 * y2))
  y2

Firefoxes performance now matches Chormes (not much improved on Chrome)

• Firefox 27.0.1
  • 1 Million fast inverse sqrt = 2.5 seconds
  • 1 Million inverse sqrt = half a second
• Chrome 33.0.1750.152
  • 1 Million fast inverse sqrt = 2.4 seconds
  • 1 Million inverse sqrt = 1 second