| Revision as of 18:43, 11 May 2020 editDannyS712 bot (talk | contribs)Bots129,523 editsm Task 70: Update syntaxhighlight tags - remove use of deprecated <source> tagsTag: AWB← Previous edit | Revision as of 11:15, 12 November 2020 edit undoMajavahBot (talk | contribs)Bots33,649 editsm Bot: Fill missing DYK blurbNext edit → | ||
| Line 13: | Line 13: | ||
| |action2oldid=280679702 | |action2oldid=280679702 | ||
| |dykentry=... that '']'' ''']''' code uses a "magic number" to generate a quick first approximation to ] of ]? | |||
| |dykdate=23 February 2009 | |dykdate=23 February 2009 | ||
| |currentstatus=GA | |currentstatus=GA | ||
Revision as of 11:15, 12 November 2020
 | Fast inverse square root has been listed as one of the Mathematics good articles under the good article criteria. If you can improve it further, please do so. If it no longer meets these criteria, you can reassess it. | |||||||||||||||||||||
| ||||||||||||||||||||||
 | This article has not yet been rated on Misplaced Pages's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
{{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
{{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
| ||||||||||||||||||||||||||||
 Archives |
Re-organization of the article
I have rewritten a significant fraction of the article, and shifted some other pieces around. The main reason for doing this is that I felt that, as it was, the article had too many long and hard to read equations which obscured the very essential point of the algorithm. Namely, that aliasing an int to a float is a quick and dirty approximation of its logarithm. From this, everything else derives trivially. I tried give this point a more central place in the article, and also provided a graph comparing Ix with a scaled and shifted log2(x). The other significant changes I made are:
- I removed the figure about two's complement numbers, as it is essentially irrelevant to the point.
- I moved the worked example up: This example gives absolutely no clue of why this works, it only serves to give some “feeling” of how it works. It is then probably better to have it before we go into providing insights on the math.
- I move the Accuracy section after Newton's method, because it discusses the accuracy of the whole algorithm (including the Newton iteration), not only of the first steps.
— Edgar.bonet (talk) 12:05, 25 July 2014 (UTC)
- LGTM, thanks. Protonk (talk) 18:25, 25 July 2014 (UTC)
Poor figures
There are two figures in this article that do not have axis labels and no description of the axes is given in the figure captions. As such, they are essentially useless because you cannot tell what they mean. They should be corrected or removed, and the the perpetrators should be rapped across the knuckles, then tarred and feathered for their shoddy work. http://xkcd.com/833/
128.174.127.111 (talk) 15:21, 30 September 2014 (UTC)
- You should add some! The first one is literally just numbers against numbers. There's no real meaningful axis label unless you want to say "this here is an integer" and "this here is the floating point representation". The second one does need axis labels, as it is measuring error, but you can certainly add them to the caption (or the figure if you'd like to update the file itself). Protonk (talk) 15:32, 30 September 2014 (UTC)
I committed the first of these graphs, and I am aware of the missing axis labels. There are two curves in the graph, as identified by the key in the top-left quadrant:
- Ix
- L log2(x) + L (B − σ)
I did not label the y-axis because it can represent two different things. I could put a label like “Ix or L log2(x) + L (B − σ)”, but I really do not believe this would have any usefulness. As for the x-axis, the appropriate label would be just “x”, as this is the name given to the independent variable in the two expressions above. Would such a label be useful? — Edgar.bonet (talk) 12:53, 1 October 2014 (UTC)
The other 2 constants
This article goes into considerable depth over the optimization of the "magic constant", but ignores the other 2. Jan Kadlec wrote a program to see if he could optimize all three. After an exhaustive search:
float inv_sqrt(float x)
{ union { float f; uint32 u; } y = {x};
y.u = 0x5F3759DFul - (y.u >> 1);
return 0.5f * y.f * (3.0f - x * y.f * y.f); }
becomes:
float inv_sqrt(float x)
{ union { float f; uint32 u; } y = {x};
y.u = 0x5F1FFFF9ul - (y.u >> 1);
return 0.703952253f * y.f * (2.38924456f - x * y.f * y.f); }
With all 3 parameters optimized, you can get min max error = 0.0006501967. All the details can be found here. — Preceding unsigned comment added by Slacka123 (talk • contribs) 06:02, 7 April 2015 (UTC) ; edited 09:26, 7 April 2015 (UTC)
The algorithm that explains the magic number
I revised my document (referenced in this article), http://www.geometrictools.com/Documentation/FastInverseSqrt.pdf, which now describes a minimax algorithm that almost generates the magic number. By "almost" I mean: whoever wrote the original code probably estimated the minimax value using sampling. The code's magic number and the value I computed by implementing the minimax algorithm are nearly the same number. The algorithm is more general in that the initial guess to Newton's method is y0 = a + b*x. The first iterate is y1 = y0*(3-x*(a + b*x)^2)/2, which can be thought of as a function of 'a' and 'b'. For each (a,b), the relative error in the approximation is E(a,b) = max_{x in [1,2)}|sqrt(x)*y1-1|. If you minimize this for all a > 0 and b < 0, you obtain an error bound about half that produced by the Quake3 code, but the implementation is slower (but still faster than 1/sqrt(x)). If you constrain the problem by choosing b = -1/4 and compute the minimum of E(a,-1/4), you get an 'a' that generates a magic number nearly the same as the Quake3 code, but the global error bound is slightly smaller (which argues the code writer estimated the minimizer for 'a'). Lomont's document attempts to explain with a minimax algorithm, but for y0 fitted to 1/sqrt(x); however, the goal is for y1 to be a good estimate. Just thought I'd mention this in case whoever likes updating the main page can feel free to do so. Daveeberly (talk) 20:26, 9 May 2015 (UTC)
- I've gone ahead and updated the reference, especially since the document at the link is the new one. Other than that, was there another reference in the article you thought needed updating? Rwessel (talk) 04:32, 10 May 2015 (UTC)
Earliest reference
In the 1990 Graphics Gems 1 book, Paul Lalonde and Robert Dawson of Dalhousie University, Halifax, Nova Scotia share code for the fast sqrt and inverse sqrt. The method they describe is more verbose but effectively the same as the modern code, though they don't use the exact optimized magic constant. Clearly the constant is just a refinement from the basic structure they discribe. https://imcs.dvfu.ru/lib.int/docs/Programming/Graphics/Graphics%20Gems%20I.pdf See the chapter "A HIGH SPEED HIGH SPEED, LOW PRECISION PRECISION SQUARE ROOT QUARE ROOT"
http://www.realtimerendering.com/resources/GraphicsGems/gemsiii/sqrt.c — Preceding unsigned comment added by 76.102.116.190 (talk) 02:31, 9 October 2016 (UTC)
- The code your are referring to is based on a table lookup. It has no relationship whatsoever with the algorithm described in this article. — Edgar.bonet (talk) 09:43, 10 October 2016 (UTC)
- The code is now attributed to Greg Walsh (Ardent), who was inspired by Cleve Moler (MathWorks). Greg consulted at Kubota with Gary Tarolli.
References
"the general method to compute the inverse square root was to calculate an approximation for 1/√x" ?
In the section "Overview of the code", there is the expression:
At the time, the general method to compute the inverse square root was to calculate an approximation for 1/√x, then revise that approximation via another method until it came within an acceptable error range of the actual result.
The word "at the time" looks to mean the method before fast inverse square root. However, the expression also matches the fast method. The method just uses special way to calculate an approximation for 1/√x. I think the past method was to calculate the multiplicative inverse and then to calculate the square root of it (it can be reversed). It should be clarified in the article. Gjhdvhd (talk) 09:44, 23 October 2016 (UTC)
Point of the Method?
This article starts motivating the algorithm by stating
At the time, it was generally computationally expensive to compute the reciprocal of a floating-point number
This suggests that the point of the algorithm is to avoid the cost of computing the inverse (of the square root). However, it rather seems that the point of the algorithm is to avoid having more than one Newton iteration. — Preceding unsigned comment added by 79.210.119.29 (talk) 02:21, 28 April 2017 (UTC)
Standard square root?
Is there a similar method to calculate normal square root? — Preceding unsigned comment added by 2A01:119F:21D:7900:A5CD:B2BA:D621:91CF (talk) 09:38, 2 December 2017 (UTC)
Proposal to Protect Page
I'd like to propose protecting this page under "Pending changes" (WP:PEND). Looking at the edit history, almost every "Undo" for the past year is reverting someone's removal of the profanity in the algorithm's code comments. Further, many of the undone edits are by new or unregistered users. Ignoring these, I see about 2 accepted edits per month, which seems infrequent. The page protection guidelines state that WP:PEND is appropriate for "nfrequently edited articles with high levels of vandalism ... from unregistered and new users", which seems appropriate for this page. I realize the profanity edits are made in good faith and aren't actual vandalism, but they're still disruptive. If there is some way to protect just the code block, that would be better, but I don't know of one. Decka7 (talk) 15:55, 20 November 2018 (UTC)
- I'd agree, but protecting a portion only is not facilitated. However, instead of presenting the notorious original as text, which is easily edited, it could be presented as an image of such text which is not so easy to edit in part. The image file might be protected from deletion itself. So, does someone have access to an image of the original source file, as printed then? Or will an image of the current source do, via a screen grab? NickyMcLean (talk) 02:08, 13 March 2019 (UTC)
Accuracy claim
Under accuracy it claims a worse case error of 1.7% When I run the algorithm I get a worse case relative error of 0.00174915. Ie 0.17% Has the article simply shifted the decimal place? It would be nice is someone else could double check.
Bill W102102 (talk) 09:57, 12 March 2019 (UTC)
- One of the features of the much-vaunted metric system is the ease with which powers of ten or factors of a thousand are miscounted. Here, although not involving Systeme International, by chance, the example used is the rather boring number 0·01 whose square root is 0·1, and so the reciprocal is 10. The article is quoting the actual difference (x - rsqrt(x)) which is indeed 0·017478 and which, as a percentage of one is 1·7478% But the value is ten, and so the relative error is a percentage of ten and thus 0·17478% A factor of ten has been overlooked, as you say. NickyMcLean (talk) 02:08, 13 March 2019 (UTC)
Thank you BillW102102 (talk) 10:40, 13 March 2019 (UTC)
Picture of John Carmack
Is this the only Misplaced Pages article that's illustrated by a picture of a person who definitely did not do the work? How about deleting the picture? Zaslav (talk) 23:49, 5 June 2019 (UTC)
Agreed, it's nonsense to have Carmack's mugshot here. He already has his own[REDACTED] page and that image makes good sense there but here it is just noise. — Preceding unsigned comment added by 213.127.87.1 (talk) 10:02, 14 November 2019 (UTC)
Moroz Cite ref
The "Moroz 2018." citation reference doesn't seem to link properly, but I'm not sure why. —Fishrock123 (talk) 18:59, 29 January 2020 (UTC)
Categories:- Misplaced Pages good articles
- Mathematics good articles
- Old requests for peer review
- Misplaced Pages Did you know articles that are good articles
- All unassessed articles
- GA-Class video game articles
- Low-importance video game articles
- WikiProject Video games articles
- GA-Class Computer science articles
- Low-importance Computer science articles
- WikiProject Computer science articles
- GA-Class mathematics articles
- Low-priority mathematics articles