Hacker Read

mkl · 2022-12-07 15:11:00

It's way older than Quake III: https://en.wikipedia.org/wiki/Fast_inverse_square_root

Many past discussions on HN: https://hn.algolia.com/?q=inverse+square+root

hkailahi | karma 304 | avg karma 5.53 · | 2015-07-12 16:10:04+00:00

I was just talking about this paper with a coworker on Friday.

One of the best parts about this code is its initial implementation in Quake III. The comments are especially funny. It's on Wikipedia - https://en.wikipedia.org/wiki/Fast_inverse_square_root

reply

delta_p_delta_x | karma 3044 | avg karma 4.57 · | 2022-12-07 06:43:53

Also related: Quake III fast inverse square root[1].

[1]: https://github.com/id-Software/Quake-III-Arena/blob/master/c...

reply

lmm | karma 42440 | avg karma 1.91 · | 2020-01-10 00:09:27+00:00

The famous "fast inverse square root" was in Quake 3.

herodoturtle | karma 2120 | avg karma 3.15 · | 2023-09-06 01:45:05

Relevant Quake engine trivia, for those that are interested:

https://en.m.wikipedia.org/wiki/Fast_inverse_square_root

reply

ksaj | karma 2486 | avg karma 0.81 · | 2023-10-27 23:20:46

The Fast Inverse Square Root function from Quake III:

    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?

https://en.wikipedia.org/wiki/Fast_inverse_square_root

karmakaze | karma 8189 | avg karma 1.25 · | 2021-02-14 18:54:31+00:00

Of course there's "Fast Inverse Square Root — A Quake III Algorithm"

[0] https://www.youtube.com/watch?v=p8u_k2LIZyo

reply

viggity | karma 3728 | avg karma 3.08 · | 2018-11-02 13:57:46

finding an approximate root for these purposes can be really quite fast, as was demonstrated in Quake III. https://en.wikipedia.org/wiki/Fast_inverse_square_root

next_xibalba | karma 1745 | avg karma 3.97 · | 2022-07-25 08:48:03

Fast inverse square root for computer graphics programming! [1] Popularized by leaked Quake III code (attributed to John Carmack), but dates back much further.

[1] https://en.wikipedia.org/wiki/Fast_inverse_square_root

reply

H4CK3RM4N | karma 599 | avg karma 2.08 · | 2017-06-05 11:22:36+00:00

Wasn't Quake the one where they did a really good approximation of he inverse square root because they needed it?

mumrah | karma 427 | avg karma 3.05 · | 2012-02-01 14:09:40+00:00

Here's a link to the infamous fast inverse square root function: https://github.com/id-Software/Quake-III-Arena/blob/master/c...

smcl | karma 13675 | avg karma 2.97 · | 2016-03-09 10:47:50

It's a shame you picked q3's fast inverse square root. It's not a great example as it turns out someone else implemented it in Quake 3 and someone else entirely devised the algorithm itself. Though you're right - he's a bit of a hero and deservedly so.

edit: however ... I've just read that article and it is actually the most in-depth and interesting analysis I've read on the subject so thanks!

reply

EliRivers | karma 5862 | avg karma 1.69 · | 2017-06-05 11:39:58+00:00

Fast inverse square root as seen in Quake (as mentioned in other comments)

https://en.wikipedia.org/wiki/Fast_inverse_square_root#Overv...

reply

chubot | karma 15013 | avg karma 3.62 · | 2019-11-18 23:40:09

Hm interesting, I knew it from Quake and implicitly assumed that it was Carmack's trick. But Wikipedia has some more history:

https://en.wikipedia.org/wiki/Fast_inverse_square_root#Histo...

reply

speedgoose | karma 8135 | avg karma 2.13 · | 2022-04-28 11:14:44

Do we have another example than the famous quake fast square root function?

peterburkimsher | karma 4193 | avg karma 2.53 · | 2021-07-22 17:00:39

As mentioned in the article, it reminds me of the 0x5f3759df fast inverse square root used in Quake III Arena!

https://medium.com/hard-mode/the-legendary-fast-inverse-squa...

This is where I really see CS as being close to mathematics.

reply

Kwpolska | karma 3605 | avg karma 2.58 · | 2023-05-13 13:05:26

Here’s your fast inverse square root (totally not copied from Quake II Arena). By the way, did you know that I’m a real boy and I’m stuck in a code factory?

ddtaylor | karma 11964 | avg karma 5.87 · | 2018-06-13 04:13:14

Here is the famed "Fast Inverse Square Root" trick:

https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb1...

https://en.wikipedia.org/wiki/Fast_inverse_square_root

reply

peteradio | karma 2428 | avg karma 0.85 · | 2023-05-26 10:52:22

Feels very much like an appeal to authority though. Fast inverse square root was discovered/implemented as a side task for a first person shooter: https://en.wikipedia.org/wiki/Fast_inverse_square_root.

juliansimioni | karma 1676 | avg karma 25.01 · | 2023-03-14 21:00:36

I really want to see it explain the famous Quake fast inverse square root, but apparently it's extremely rate limited right now