Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fast Inverse Square Root

timmmm.github.io

Post reply on HN
Print view View original

41–50 of 100 posts

Re: Fast Inverse Square Root

#41

Post by gruez »

person_of_color wrote: post #38

What was the speedup from this? If only 1% of cpu time was spent on slow square root, and this sped it up by 100%, it would be barely worth it.

It was first found in quake 3, which I believed used software rendering. Given that inverse square root is heavily used for lighting functions, and it was all done in CPU, it's reasonable to believe that this provided a non-negligible speedup overall.

Re: Fast Inverse Square Root

#43

Post by amatic »

Greek0 wrote: post #5

Here's another article (from 2012) describing the same calculation: http://h14s.p5r.org/2012/09/0x5f3759df.html

The original article has the same error in the title. x^(-1/2) is the reciprocal square root. The fault is with math notation where rasing x to a negative power, i.e. x^-a means 1/(x^a); while inverse function F(x) is written F^-1(x). The inverse square root would be just square. Edit: I saw it called multiplicative inverse of the square root

Re: Fast Inverse Square Root

#44

Post by grecy »

person_of_color wrote: post #38

What was the speedup from this? If only 1% of cpu time was spent on slow square root, and this sped it up by 100%, it would be barely worth it.

I've always wondered too if it would be possible to log all the values it's actually calculating the inverse square root for, and just save them in a lookup table. Or even just the most common x% of them if you could reliably know for which numbers its most commonly running the calculation on.

Re: Fast Inverse Square Root

#45

Post by Kranar »

TwoBit wrote: post #34
colejohnson66 wrote: post #27

Earlier quoted context omitted.

In C++, type punning through pointers and unions is undefined behavior. Even `reinterpret_cast ` isn’t allowed because of aliasing (IIRC). The only “defined” way to do type punning is a memcpy. A compiler targeting something like x86 would optimize out the memcpy. For more information, see the C++20 final draft[0§7.6.1.9] [0]: https://isocpp.org/files/papers/N4860.pdf

I really wish C and C++ had an explicit type punning operator. They are systems programming languages and this is very often needed.

C++20 introduces bit_cast to do this. The implementation of bit_cast is semantically equivalent to using memcpy.

Re: Fast Inverse Square Root

#46

Post by Kranar »

taneq wrote: post #39
person_of_color wrote: post #38

What was the speedup from this? If only 1% of cpu time was spent on slow square root, and this sped it up by 100%, it would be barely worth it.

I don't know how heavily it was used in Quake but I'd bet quite a lot. Carmack didn't mess around optimizing things for no reason, he was (and is) pretty focused on spending time (coder and CPU) where it will do most good. Also, a "mere" 1% speedup seems trivial for most general coding but squeezing 1% out of optimized game code is like blood from a stone. Add a bunch of similar tricks together and you can see 10-20%…

I mean it's now ingrained in programming lore, but the reality is that Carmack has nothing to do with this and Carmack himself has never taken credit for it. The fast inverse square root dates back to the 80s and has its roots in SGI's systems. One of the developers who worked at SGI would eventually go on to work at ID developing Quake and worked on this optimization.

Re: Fast Inverse Square Root

#47

Post by nwallin »

person_of_color wrote: post #38

What was the speedup from this? If only 1% of cpu time was spent on slow square root, and this sped it up by 100%, it would be barely worth it.

> and this sped it up by 100%

Over 1,000%.

x87 fsqrt took ~70 cycles on the Pentium MMX x87, x87 fdiv was ~39 cycles - so doing inverse square root on x87 was ~109 cycles. The fast inverse square root routine was in the vicinity of 10 cycles.

In Quake, each vertex needed to have its normal vector calculated, which resulted in... I dunno, 100,000 inverse square root calculations per second, assuming you're pushing 100,000 polygons per second. Assuming a 100MHz CPU, the x87 inverse square root calculations would consume 11% of the CPU cycles, the fast inverse square root routine would consume 1% of the CPU cycles.

https://en.wikipedia.org/wiki/X87#Performance

Re: Fast Inverse Square Root

#48

Post by User23 »

timhh wrote: post #2

This is an explanation of the fast inverse square root that I hope is easy to understand. I also managed to improve on it a little bit.

Very nice piece! Also, minuend and subtrahend are the standard terms.

Re: Fast Inverse Square Root

#49

Post by copascetic »

TwoBit wrote: post #33
usmannk wrote: post #8

Earlier quoted context omitted.

Interestingly enough it seems to do the shift first in Swift

All well-known programming languages will do the shift first.

C, C++, Java, and Rust all have shift as lower precedence than addition/subtraction. Edit: and Javascript, Python.

Re: Fast Inverse Square Root

#50

Post by enriquto »

TwoBit wrote: post #34
colejohnson66 wrote: post #27

Earlier quoted context omitted.

In C++, type punning through pointers and unions is undefined behavior. Even `reinterpret_cast ` isn’t allowed because of aliasing (IIRC). The only “defined” way to do type punning is a memcpy. A compiler targeting something like x86 would optimize out the memcpy. For more information, see the C++20 final draft[0§7.6.1.9] [0]: https://isocpp.org/files/papers/N4860.pdf

I really wish C and C++ had an explicit type punning operator. They are systems programming languages and this is very often needed.

Casting pointers in C used to work back in the day. It still works in most cases (except with aggressive optimization options), but it may may make some people uneasy.
Post reply on HN