"The fast inverse square-root algorithm: bit-witchery from a more elegant age"

Amit Halevi
Oct 13 2015 - 12:30pm
Event type: 
Graduate Student Seminar
214 Fine Hall

Even though we've long since passed the days where calculating x^(-1/2) was an expensive operation, computation mathematics remains yoked to the burden of computational load.  The fast inverse square root algorithm is a classic example of a very cheap approximation of an expensive operation, using an underlying understanding of how numbers are stored and processed in a computer and some bit-level hacking.  This talk will provide an overview and explanation of the algorithm, discuss some of the concepts needed to understand how it works (in particular, the contrast between fixed and floating point numbers in computation), and bound the error of the approximation.