71–80 of 100 posts
To me "inverse square root" means "square" so it makes the title of this kind of funny.
No, it's completely different than simple squaring. The inverse square root is undefined for negative numbers ;)
You're not the only one to be confused by the name. An awful choice of name, in my opinion.
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.
Small nitpicks: > But floating point numbers are always greater than LNS numbers Unless I'm missing something, they are never smaller, but they can be equal (at powers of two). > E.g. x1/2x^{1/2}x1/2, x−8x^{-8}x−8, x2x^2x2, though you probably wouldn't use it for positive exponents since you can just use multiplication to get an exact answer. 1/2 is positive. As is 1/3.
Ha, funnily enough I did think of that, but I was trying to keep the explanation short and simple (and a bit hand-wavy).
> 1/2 is positive. As is 1/3
Oops, fixed, thanks!
Earlier quoted context omitted.
All well-known programming languages will do the shift first.
I looked at about 20 different "popular" languages and I believe that only 2 (Go and Swift) of them have shifts at a higher precedence than addition. I think I'm missing a reference/joke =/
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.
If you can do 10,000 things with 1% cpu time, and you are now able to do 5,000 more things, is it still not worth it?
Earlier quoted context omitted.
XKCD is legit shit. This one, the standards one, the Bobby Tables one. And the password one. Things that are barely worth a chuckle are repeated as gospel.
Wow, bruh, who hurt you?
> Games calculate square roots and inverse square roots all the time to find the lengths of vectors A trick here is that one often doesn't have to do the square root. For instance, if you want something to happen when an object is 5 units away from another object, it's normal to do if sqrt( (x2-x1)^2 - (y2-y1)^2 ) but instead you can do if (x2-x1)^2 - (y2-y1)^2 trading a sqrt for a squaring. And often the square of t…
Sometimes you can even get away by dropping the square completely: if (x2-x1) - (y2-y1) I once used this in a path tracer to speed things up a little. The results where less accurate but sometimes this can be used as trade-off.
Earlier quoted context omitted.
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.
A little self-promotion: I've written a blog post to answer the question that this one ends with (how to optimize divisions by constant integers): https://rubenvannieuwpoort.nl/posts/division-by-constant-uns... https://ridiculousfish.com/blog/posts/labor-of-division-epis... and https://ridiculousfish.com/blog/posts/labor-of-division-epis... also explain this (and are probably better written than my blogpost).
Minor nit, there's a typo here in the power-of-two example:
uint divide(uint n) {
return n