51–60 of 100 posts
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.
Computers do not have _real_ number systems, only _rational_ number systems and rational approximations of real numbers.
Earlier quoted context omitted.
Computers do not have _real_ number systems, only _rational_ number systems and rational approximations of real numbers.
There are plenty of libraries for computable numbers [1], which sit between the rationals and reals [1] https://en.wikipedia.org/wiki/Computable_number
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.
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).
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
There's a Torvalds rant about this specific UB and it's how they do it in the Linux kernel.
It’s C++ that’s lacking this feature. Not C.
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.
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 for host architecture and compare the fixed point result to host's floating point. Then I can set a precise error margin for my XP approximation.
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).
For anyone curious like I was:
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.