Quake 3 inverse square root8/14/2023 ![]() However, we still need to convert between C data types and Python data types as we can't do arithmetic on C types from within Python itself. ![]() This makes it useful for implementing the Fast Inverse Square Root method where we really need to work with data types which Python lacks. The ctypes library lets you create native C data type values in Python (int32, float16, pointers) so you can delgate hard work to C code. ![]() Other than that, I'll stick as close as possible to the lines of the C function for the purpose of exposition. The other difference is that my functions will take Python float objects as input and also return a Python float object. I'll do the same in the Python functions below. This function uses one iteration of Newton's method to improve the accuracy of the returned float value. Y = y * ( threehalfs - ( x2 * y * y ) ) /* Newton's method */ return y Ĭompiling this function and using the float 16.0 as my input, I get back a value of 0.24957679212, close to the expected value 0.25. However, the algorithm was used much earlier than this - Wikipedia gives Gary Tarolli's implementation for the SGI Indigo as a possible earliest known use. Y = * ( float * ) &i /* int back to float */ The fast inverse square root algorithm is probably best known for its use in Quake III Arena, the source code of which was released to the public a few years after its release. I'll base the Python functions on the following C implementation of the Fast Inverse Square Root method taken from Wikipedia: Nor does it let you say anything like "the bytes of this float are to be read as an integer". Moreover, Python doesn't provide any straightforward way to locate and access the right part of your program's memory to get at the raw bits of a number. A Python float is more than simply 32 or 64 bits of memory: it has attributes and methods attached, as well as meta-data such reference counts (for memory management). Python doesn't use plain machine types like 32 bit integers and floats it uses its own boxed-type objects instead. We can point to a memory location (using a pointer) and say "read those bits as an integer" or "read those bits as a float" and carry on working. This reinterpretating of memory is very easy in a language like C. The Fast Inverse Square Root method hinges on quickly reinterpreting the bits of a float as an integer, doing simple arithmetic on that integer, and then reinterpreting the bits of that integer as a float. I maintain that you should always stick to x ** -0.5, but feel free to try them for speed. With that said, it's still fun to think up ways to implement the method in Python. Besides, if you're trying to optimise your number-crunching Python code to this level of hackery, you should probably choose another language for your project. It will be much faster than any custom function and probably a lot more accurate too. If you've marvelled at the Fast Inverse Square Root method and want to use this piece of witchcraft to speed up your Python code, stop! Just stick with writing x ** -0.5. It's a very common calculation in computer graphics, for example, where you need to normalise a lot of vectors. For example, put in 25, you'll get back 0.2: the square root of 25 is 5, the inverse of 5 is 1/5, or 0.2 in decimal notation. The inverse square root of a number x is x -1/2. Jumping through hoops to write the famous Quake 3 code in Python.
0 Comments
Leave a Reply.AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |