Boiledbeans

Drama! Intrigue! Geekiness!

November 30, 2009

I’m enrolling for PhD

devadutta @ 11:59 pm, GMT +0000 ( 1259625585 ) Play

Guest question from Logik. Thanks dude! Your GQHero trophy has been delivered to your house ;)

Connect

Quake_III_Arena_q3dm0

academia_vs_business

225px-GodfreyKneller-IsaacNewton-1689

Cracked by: sidsen , Raghuvansh , Jean Valjean , krudebox , Dibyo , yaksha , Logik , shashank , shrik , Ps , SV , joe , udupendra , shenoyvarun86 , Rogi , p vs np , byslexia , AC , akhi , umang , madhur , Anubhav and Ananth

Answer:

The super fast inverse square root function from Q3A. Contrary to what many of you think, this piece of code was _not_ written by Carmack. See this http://www.beyond3d.com/content/articles/8/

Quoting Logik for details

The strip makes a reference to the Newton method for calculating inverse square roots.

from:
http://www.explainxkcd.com/2009/11/18/academia-
vs-business/

0×5f375a86 is the value used in the algorithm to approximate the solution to the square root of an unsigned floating number, also known as fast inverse square root.
The solution uses an ingenious first approximation and the difficult problem was solved without any fanfare (like in the cartoon) for the game, Quake III Arena.
0×5f3759df is also used, which is found to be less accurate.
http://en.wikipedia.org/wiki/F…..quare_root


24 Responses to “I’m enrolling for PhD”

  1. sidsen
    2

    fast inverse square root


  2. Raghuvansh
    1
    9
    4

    Fast inverse square root, aka 0x5f3759df – implemented in the Quake III code, using Newton’s method. Referenced in the xkcd comic shown.


  3. one of the famous examples of an elegant piece of code locked away in proprietary source code is the fast inverse square root method(0x5f375a86) which was used in Quake 3. The connection to Newton being that the algorithm generates reasonably accurate results using a unique first approximation for Newton\’s method for finding roots of real valued functions.


  4. krudebox
    1

    Carmack’s Unusual Inverse Square Root or 0x5f375a86 is the algorithm to approximate the solution to the square root of an unsigned floating number, also known as fast inverse square root.
    The solution uses an ingenious first approximation for Newton’s method and the difficult problem was solved without any fanfare (like in the xkcd cartoon) for the game, Quake III Arena.


  5. Dibyo
    11
    14
    10

    0×5f3759df.

    john carmack is god, twice over, now.


  6. yaksha
    1
    3

    quakes fast invsqrt()


  7. Logik
    1
    5
    3

    The strip makes a reference to the Newton method for calculating inverse square roots.

    from:
    http://www.explainxkcd.com/2009/11/18/academia-
    vs-business/

    0x5f375a86 is the value used in the algorithm to approximate the solution to the square root of an unsigned floating number, also known as fast inverse square root.
    The solution uses an ingenious first approximation and the difficult problem was solved without any fanfare (like in the cartoon) for the game, Quake III Arena.
    0x5f3759df is also used, which is found to be less accurate.
    http://en.wikipedia.org/wiki/F.....quare_root


  8. 0x5f3759df or Fast inverse square root


  9. shrik
    10
    7
    9

    0x5f375a86 (from the alt-text) of xkcd 664 s the algorithm to approximate the solution to the square root of an unsigned floating number, also known as fast inverse square root. The solution uses an ingenious first approximation of Newton’s Method and the difficult problem was solved without any fanfare for the game, Quake III Arena.

    Largely taken from explainxkcd – xkcd connects are too easy ‘cos of that site :D


  10. Ps

    0×5f3759df

    Newtons Approximation of roots a concept that quake ever so happily uses


  11. Ps

    Just in case the solution is supposed to be bigger

    http://forums.xkcd.com/viewtop.....p;start=80


  12. SV
    1

    The fast inverse square root method used in Quake III is good first guess used with Newtons approximation, which got onto xkcd


  13. joe

    The fast inverse sq. root method by John Cormack, used in quake 3, referenced in the xkcd alt text and uses Newton’s method.


  14. udupendra
    4
    4
    7

    Fast inverse square root – used in Quake III, the hexcode appeared in the xkcd alttext and it is derived from the Newton’s method of approximation


  15. Straight from explainxkcd.com
    (p=np problem) 0x5f375a86 is the algorithm to approximate the solution to the square root of an unsigned floating number, also known as fast inverse square root(Newton’s method). The solution uses an ingenious first approximation and the difficult problem was solved without any fanfare (like in the cartoon) for the game, Quake III Arena.


  16. Rogi
    48
    10
    5

    Is *0x5f3759df* enough of an answer?
    (Though *0x5f375a86* is a more accurate value for use in Newton approximations for fast inverse square root operations.)


  17. The title of that XKCD strip is:
    “Some engineer out there has solved P=NP and it’s locked up in an electric eggbeater calibration routine. For every 0x5f375a86 we learn about, there are thousands we never see.”

    The 0x5f375a86 is a reference to Carmack’s implementation of the FInvSqrt() in Quake III Arena. The transformation is based on of Newton’s many approximations.

    Nice question :)


  18. byslexia

    Fast inverse square root algorithm.
    Famously used in Quake 3, referenced by xkcd. The algorithm uses Newton’s method.


  19. AC

    Good one!
    Connect : the magic number 0x5f3759df

    1) The number is used by John Carmack in Quake source code while calculating inverse square root.

    2) The number is used in the title text of that xkcd strip.

    3) The number is used as a first guess in the first iter of Newton’s approx of roots method.


  20. akhi
    2
    1

    the very fast inverse square root subroutine by Carmack.


  21. umang

    Fast inverse square root function


  22. madhur
    1

    Fast Inverse Square root!


  23. Connect – Fast inverse square root

    1. quake 3 implements a specific fast inverse square root function which attracted a lot of attention for being clever
    2. magic number in same is referenced in the xkcd comic.
    the comic itself also loosely refers to a similar situation.
    3. Newton’s method for finding roots is used in the same.


  24. Ananth
    4
    5
    9

    The square root code that is hidden inside Quake. John Carmack.


« Previous « Surf along « | » ..and the transmission is cracked! » Next »