Skip to content

Instantly share code, notes, and snippets.

@JasonGiedymin
Created June 20, 2011 20:43
Show Gist options
  • Save JasonGiedymin/1036533 to your computer and use it in GitHub Desktop.
Save JasonGiedymin/1036533 to your computer and use it in GitHub Desktop.
CoffeeScript Javascript Fast Inverse Square with Typed Arrays
###
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()
@Janther
Copy link

Janther commented Mar 28, 2014

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment