Someone found such a code to seek square root in the source code of Quake III:
/ * ================ squareroatfloat ========================== * / FLOAT SQUAREROOTFLOAT (FLONG i; float x, y; const float f = 1.5F; x = number * 0.5f; y = number; i = * (long *) & y; i = 0x5f3759df - (i >> 1); // pay attention to this line Y = * (Float *) & i; y = y * (f - (x * y * y)); y = y * (f - (x * y * y)); return number * y;}
0x5f3759df? What is this? Learning numerical analysis, I know that the algorithm is generally used by the square root, such as the unlimited approximation.
Newton iterative method, sorry, I was too bad in the year, and I can't tell. Simply speaking, the square root of 5, choose a guess, such as 2, then we can do this
5/2 = 2.5; 2.5 2/2 = 2.25; 5 / 2.25 = xxx; 2.25 xxx / 2 = xxxx ...
This is repeatedly iterated, and the result must converge in SQRT (5), it is right, and the general seeking square root is calculated. The difference between Kamark is that he chose a mysterious guess value 0x5f3759df as a start, so that the convergence of the entire approximation process has skyrocketed, and the accuracy 10 of the Quake III is 10 times, only one iteration can be obtained. result. Ok, if this is still not a cow B, then look. Chris Lomont of the University of Purdue University saw fun, decided to study what the mystery of this guess value made by Kamark. Lomont is also a cow, and since theoretically derived a best guess value after careful research, the number of Carmark is very close, 0x5f37642f. Kamark is really cattle, is he an alien? Legends have not ended here. Lomont calculates the results very satisfied, so I have the starting value and the mysterious digit of Kamak, and see who the number can make square roots faster. The result was Kamark Win ... No one knows how Kamark found this figure. Finally, Lomont was angry, using a violent method, a number of numbers tried, finally found a number than the Kamark number to be good, although the results of these two numbers were very close, this violence derived Is 0x5f375a86. Lomont write a paper for this, "Fast Inverse Square Root". John Carmack, Id invaluable treasure.
Source BLOG: http://jan.yculblog.com/
