7 ms·
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.
by timhh 6y ago
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.
- recursive 6y agoThanks 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.
- usmannk 6y agoInterestingly enough it seems to do the shift first in Swift
- TwoBit 6y agoAll well-known programming languages will do the shift first.
- thehobgoblin 6y agoI 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 =/
- hemdawgz 6y agoOr this might just be another confident but baseless HN commenter assertion.
- copascetic 6y agoC, C++, Java, and Rust all have shift as lower precedence than addition/subtraction. Edit: and Javascript, Python.
- recursive 6y agoYou can add C# as well.
- beached_whale 6y agoUse brackets to be explicit about your expected order of operations.
- timhh 6y agoOops! I added brackets, thanks!
- x3n0ph3n3 6y agoComputers do not have _real_ number systems, only _rational_ number systems and rational approximations of real numbers.
- jackpirate 6y agoThere are plenty of libraries for computable numbers [1], which sit between the rationals and reals [1] https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number
- lifthrasiir 6y ago...which (naturally) can't determine if some number x is equal to y or not; that alone makes using constructive real numbers challenging and the usage is virtually non-existent. I believe the most-known software using them is the Android calculator since 6.0 and Hans Boehm (of the gc fame) documented various issues encountered [1]. [1] https://dl.acm.org/doi/fullHtml/10.1145/2911981 https://dl.acm.org/doi/fullHtml/10.1145/2911981
- longemen3000 6y agoNice, i was looking at this, but for sqrt (basically the same integer trick)
- User23 6y agoVery nice piece! Also, minuend and subtrahend are the standard terms.
- sika_grr 6y agoYou 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?
- timhh 6y agoI 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!
- tomstuart 6y agoThis is a great post! The setup could be clearer: I found it a little difficult to follow (during “a real number x … this value which I will denote f … treat the 31-bit value as an unsigned integer u”) what each of the named variables was intended to refer to, and formatting the 31-bit number as 32 bits threw me off too. Nothing insurmountable but I could feel my brain stumbling before I got to the clever part.