There's a well-known “hack” that approximates an inverse square root (i.e., 1/x^0.5, or x^-0.5) with just a few adds, subtracts, a shift, and a multiply – and the “magic” hex constant 0x5f3759df. On hardware lacking single-cycle floating point operations, this is remarkably efficient compared with the conventional approach. I've used it myself, about 10 years ago, to speed up calculations in a Monte Carlo bond valuation simulation. It was one of the few algorithms I've ever used whose inner workings were a complete mystery to me.
But it's a mystery no more, thanks to a lovely blog post on Hummus and Magnets, by Christian Plesner Hansen. This post also links to a nice Wikipedia article on the same subject. I'm left in awe of the inventor's cleverness – the insight that the floating point's bit pattern could be mathematically manipulated is a classic hacker's trick. And now I have a new tool in my hacker kit, as I've discovered that the algorithm can be extended to cover any power between -1 and 1. Awesome!
No comments:
Post a Comment