Quake 3’s Fast Inverse Square Root Function
Note: This is not meant to be an authoritative mathematical description, and I’m pretty late to the party.. I was experimenting with the code, and am scratching an itch. For a far superior description, please look at Chris Lomont’s excellent analysis.
The Infamous Code
x2 = number * 0.5F; y = number; i = * ( long * ) &y; i = 0x5f3759df - ( i >> 1 ); y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // y = y * ( threehalfs - ( x2 * y * y ) );
The Function to Model
How Did the Authors Think of This?
Interestingly, this method is nearly identical to one from a mathematical text called “An Introduction to Numerical Analysis
My Numerical Methods book for this semester contains the full derivation of the method from “An Introduction to Numerical Analysis” that uses linear interpolation for an initial guess to Newton’s Method that gives the accuracy of the function to provably under 4.7E-14 for four iterations. Chris Lomont’s paper goes into much more detail about the method for choosing a suitable constant that the “Quake 3″ authors likely used. Linear interpolation gives a fairly good guess, but it’s possible to take advantage of the way the constant is stored to give us a much better guess. As you can see below, the guess isn’t linear, but actually fits the curve very well without any iterations of the Newton-Rhapson method.
The initial guess is very good. How good? It nearly overlaps the function. The guess is added in red:
I was going to compare the output of the Quake 3 method with the real output, but it was difficult finding a view where there was any very noticeable difference at all, so suffice it to say that it is very close.
from: http://www.jakevoytko.com/blog/2008/01/28/quake-3s-fast-square-root-function/
标签：inverse sqrt root相关日志
If you enjoyed this post, please consider to leave a comment or subscribe to the feed and get future articles delivered to your feed reader.
