Newton's Method
After performing those integer operations, the algorithm once again treats the longword as a floating point number (x = *(float*)&i;) and performs a floating point multiplication operation (x = x*(1.5f - xhalf*x*x);). The floating point operation represents a single iteration of Newton's method of finding roots for a given equation. For this example,
- is the inverse square root, or, as a function of y,
- .
- As represents a general expression of Newton's method with as the first approximation,
- is the particularized expression where and .
- Hence
x = x*(1.5f - xhalf*x*x);is the same as
The first approximation is generated above through the integer operations and input into the last two lines of the function. Repeated iterations of the algorithm, using the output of the function as the input of the next iteration, cause the algorithm to converge on the root with increasing precision. For the purposes of the Quake III engine, only one iteration was used. A second iteration remained in the code but was commented out.
Read more about this topic: Fast Inverse Square Root
Famous quotes containing the words newton and/or method:
“Glorious things of thee are spoken, Zion city of our God!
He, whose word cannot be broken, Form’d for thee his own abode:
On the rock of ages founded, What can shake thy sure repose?
With salvation’s walls surrounded Thou may’st smile at all thy foes.”
—John Newton (1725–1807)
“Argument is conclusive ... but ... it does not remove doubt, so that the mind may rest in the sure knowledge of the truth, unless it finds it by the method of experiment.... For if any man who never saw fire proved by satisfactory arguments that fire burns ... his hearer’s mind would never be satisfied, nor would he avoid the fire until he put his hand in it ... that he might learn by experiment what argument taught.”
—Roger Bacon (c. 1214–1294)