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

61–70 of 100 posts

Re: Fast Inverse Square Root

#61

Post by DoingIsLearning »

colonwqbang wrote: post #58

> [Fixed point arithmetic] has some niche uses but isn't commonly used It is very common in the embedded world and in hardware. I routinely program a CPU which has no FPU, so any arithmetic will have to be done in fixed point. It's perfectly possible to get work done with fixed point arith, it just requires a bit more thinking through so you don't run out of bits. Usually, I write unit tests where I compile my code f…

Another 'niche' use case is doing DSP calculations on an FPGA. If you can accept the trade-off of some degree of error with fixed-point, you can have very fast and heavily parallelized implementations.

Re: Fast Inverse Square Root

#62

Post by andi999 »

colejohnson66 wrote: post #27
qppo wrote: post #21

Earlier quoted context omitted.

That's the Linux way to do it union { int i; float f } u { .f = 1.23f }; int i = u.i; Another way is a memcpy, which I believe is the most defined way to do type punning int i; float f; memcpy(&i, &f, 4); But you also have to assume the size of those primitive types but that's pretty safe in modern C/C++.

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 always thought the memcopy is optimized out, but can you explain how in int i; float f; memcopy (&i, &f,4) the memcopy can be optimized out? Probably I am misunderstanding the statement.

Re: Fast Inverse Square Root

#64

Post by matsemann »

> 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 the distance can be cached or even a constant. So a lot of libraries (for instance vector library from libgdx[0]) contain a dst function, but also a dst2 function that skips the squaring to save some cycles when not needed.

[0]: https://libgdx.badlogicgames.com/ci/nightlies/docs/api/com/b...

Re: Fast Inverse Square Root

#66

Post by DarkWiiPlayer »

DoingIsLearning wrote: post #59
rustybolt wrote: post #54

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).

Off-topic comment, I really like the clutter-free look of your site, with the latex to html generator. For anyone curious like I was: https://github.com/rubenvannieuwpoort/static-site-generator

I totally agree! It's easy to read and has a bit of a "paper" feel to it, but at the same time the sans-serif font makes it still feel "modern" and like a website.

Re: Fast Inverse Square Root

#67

Post by timhh »

recursive wrote: post #3
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.

Thanks for this. I have one nit. You show `q = 1598029824 - u/2;` as being identical to `q = 0x5F400000 - u >> 1;`, but every language I know of uses a different order of operations, giving different results. It might be clearest to provide parentheses in the second case.

Oops! I added brackets, thanks!

Re: Fast Inverse Square Root

#68

Post by MaxBarraclough »

drinkwell wrote: post #22
zeroonetwothree wrote: post #20

To me "inverse square root" means "square" so it makes the title of this kind of funny.

Yeah, shouldn't it be 'fast reciprocal square root'?

Agreed. Inverse is not a synonym for reciprocal, but it's too late, the name has stuck.

Re: Fast Inverse Square Root

#69

Post by thdrdt »

matsemann wrote: post #64

> 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.

Re: Fast Inverse Square Root

#70

Post by timhh »

sika_grr wrote: post #53
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.

You mention the wiki page is badly written, and I have the same feeling whenever I read about anything mathematics related on it. But... it's written by volunteers, so I'll take what I can get. Since you obviously have the talent for explaining things, do you think the wiki page could be edited and improved for clarity?

I have thought about it, but I always worry about making large edits to Wikipedia pages that I'll put a lot of work into it and then someone will come along and just revert it. Maybe that fear is unfounded - I'll put it on my (very long) todo list!
Post reply on HN