Understanding Quake's Fast Inverse Square Root

Blog Articles
1

An article and research paper describe a fast, seemingly magical way to compute the inverse square root (1/sqrt(x)), used in the game Quake.

This is a companion discussion topic for the original entry at http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/
2

For a better explanation about this, check out http://www.mceniry.net/papers/Fast%20Inverse%20Square%20Root.pdf

3

For a better explanation about this, check out http://www.mceniry.net/papers/Fast%20Inverse%20Square%20Root.pdf

4

[…] Fast inverse square root 05dec07 Beyond3D(Rys) wrote an article (almost a series!) about the history of the magic fast inverse square root found in for example the quake code. With the explantions it doesn’t seem quite that much as magic. As this pdf says, its not magic at all(page2) […]

5

Try asking this guy what text book he found it in. http://groups.google.com/group/comp.graphics.algorithms/msg/e314d9a118639bb9

6

[…] Let’s make our guess better. Archimedes discovered that adding sides made a better estimate. There are numerical methods to refine a formula again and again. For example, computers can start with a rough guess for the square root and make it better (faster than finding the closest answer from the outset). […]

7

[…] Quake’s fast inverse square root. […]

8

[…] Fast Inverse Square Root The article “fast inverse sqrt” came to my attention. It shows a small function written in C which is amazingly fast and approximates sqrt(1/x) pretty well. Appearently it was used in the Quake source code to speed up vector normalizations. But how does it work? Also, can it be improved? […]

9

[…] http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ […]

10

[…] Understanding Quake’s Fast Inverse Square Root | BetterExplained (tags: programming algorithm algorithms math mathematics) […]

11

I don’t believe you ever explained what 0x5f3759d5 is

12

I did this in band camp.

13

Kalid

I really enjoyed your explanation. Much clearer than any of the links the previous commentators have posted. I have come across this equation before and not really understood it. Now I do. Thanks.

Keep up the great work.

Alex

14

@Tim: Check out the section “So why the magic number?” near the end.

@Alex: Thanks for the comment!

15

[…] [ taken with comments from Kalid Azad @ BetterExpalined.com: Understanding Quake’s Fast Inverse Square Root ] […]

16

Indeed, a few terms of the Newton-Raphson method is how most hardware does square root, so adapting that for an inverse square root function is similar. However, for general functions there are better ways. See the HANDBOOK OF MATHEMATICAL FUNCTIONS by Abramowitz and Stegun.

17

[…] [3] http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ convert this post to pdf. Tags: [ Sem categoria ] | [ Veja este post em PDF: ] […]

18

Bit of a correction. Normalising is not actually a ‘fancy term for division’. A vector has an exact length of 1, that is, sqrt(x^2+y^2+z^2) = 1. The normalisation process takes a scalar, like a vector but with no definition of how long it should be, and makes it a vector of the same direction.

It’s important for things like lighting in computer graphics (you’ve heard of normal maps, right?), even phong shading wouldn’t work without it.

19

Thanks for putting the time and effort to give a very clear explanation. I tried to read the paper at first, but your explanation provided adequate explanation for someone who wants to get a first hand understanding that piece of code. Keep up the good work.

20

@saurabh: Thanks! I had trouble understanding the paper at first, writing down my thoughts helped make the ideas click a bit more :).