Misplaced Pages

Talk:Fast inverse square root: Difference between revisions

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editNext edit →Content deleted Content addedVisualWikitext
Revision as of 11:15, 12 November 2020 editMajavahBot (talk | contribs)Bots33,643 editsm Bot: Fill missing DYK blurb← Previous edit Revision as of 18:36, 10 January 2021 edit undo87.75.117.183 (talk) →What the fuck comment: new sectionNext edit →
Line 139: Line 139:


The "Moroz 2018." citation reference doesn't seem to link properly, but I'm not sure why. —] (]) 18:59, 29 January 2020 (UTC) The "Moroz 2018." citation reference doesn't seem to link properly, but I'm not sure why. —] (]) 18:59, 29 January 2020 (UTC)

== What the fuck comment ==

Is the comment present in the original code? Is the profanity merely gratuitous? Is its presence in this article necessary? ] (]) 18:36, 10 January 2021 (UTC)

Revision as of 18:36, 10 January 2021

Good articleFast 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.
Did You Know Article milestones
DateProcessResult
February 20, 2009Good article nomineeListed
March 31, 2009Peer reviewReviewed
November 30, 2016Featured article candidateNot promoted
Did You Know A fact from this article appeared on Misplaced Pages's Main Page in the "Did you know?" column on February 23, 2009.The text of the entry was: Did you know ... that Quake III Arena's fast inverse square root code uses a "magic number" to generate a quick first approximation to Newton's method of computing roots?
Current status: Good article
This article has not yet been rated on Misplaced Pages's content assessment scale.
It is of interest to the following WikiProjects:
WikiProject iconVideo games Low‑importance
WikiProject iconThis article is within the scope of WikiProject Video games, a collaborative effort to improve the coverage of video games on Misplaced Pages. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Video gamesWikipedia:WikiProject Video gamesTemplate:WikiProject Video gamesvideo game
LowThis article has been rated as Low-importance on the project's importance scale.
Summary of Video games WikiProject open tasks:
Summary of Video games WikiProject open tasks
AfDs Merge discussions Other discussions No major discussions Featured content candidates Good article nominations DYK nominations Reviews and reassessments
Articles that need...
Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
WikiProject iconComputer science Low‑importance
WikiProject iconThis article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Misplaced Pages. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science
LowThis article has been rated as Low-importance on the project's importance scale.
Things you can help WikiProject Computer science with:

 Here are some tasks awaiting attention:
Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
WikiProject iconMathematics Low‑priority
WikiProject iconThis article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Misplaced Pages. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
LowThis article has been rated as Low-priority on the project's priority scale.
Archiving icon
Archives

1


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)

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

  1. https://www.beyond3d.com/content/articles/15/

"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)

What the fuck comment

Is the comment present in the original code? Is the profanity merely gratuitous? Is its presence in this article necessary? 87.75.117.183 (talk) 18:36, 10 January 2021 (UTC)

Categories:
Talk:Fast inverse square root: Difference between revisions Add topic