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:
“The next Augustan age will dawn on the other side of the Atlantic. There will, perhaps, be a Thucydides at Boston, a Xenophon at New York, and, in time, a Virgil at Mexico, and a Newton at Peru. At last, some curious traveller from Lima will visit England and give a description of the ruins of St. Paul’s, like the editions of Balbec and Palmyra.”
—Horace Walpole (1717–1797)
“... [a] girl one day flared out and told the principal “the only mission opening before a girl in his school was to marry one of those candidates [for the ministry].” He said he didn’t know but it was. And when at last that same girl announced her desire and intention to go to college it was received with about the same incredulity and dismay as if a brass button on one of those candidate’s coats had propounded a new method for squaring the circle or trisecting the arc.”
—Anna Julia Cooper (1859–1964)