Content deleted Content added
Jitse Niesen (talk | contribs) →new method: comment |
Daveeberly (talk | contribs) Clarification of the fastsqrt section. Simplification of the two-variable iterative method. |
||
Line 50:
:I've been trying to find a source for it for a while to no avail. I understand IEEE but I'd have to take a close look at it to understand what's going on (it's kind of a reverse engineering problem). What we have now describes how to do it (maybe, I haven't been able to verify that it works), but not why it works. I think it's probably a valid technique, and is certainly of use to graphics programmers who may need a quick way to normalize a vector, but I haven't taken the time to look at it yet. - [[User:Rainwarrior|Rainwarrior]] 23:28, 9 September 2006 (UTC)
:If you are referring to fastsqrt, it is better to motivate the discussion without referring to log2. The explanation about computing the biased exponent for the square root needs clarification, especially because the right-shifting of the LSB of the exponent into the MSB of the trailing significand is important when motivating why the resulting significand approximates that for sqrt(x). The basic idea is let x = 1.t*2^e, where e is the unbiased exponent and t is the trailing significand. If e is even, say, e = 2*p, then sqrt(x) = sqrt(1.t)*2^p. The number 1.t represents 1+t and sqrt(1+t) is approximately 1+t/2 (use first two terms of Taylor series). The biased exponent is odd, so the subtraction of 1 produces an even number and bit 23 is a zero. The right-shift takes trailing significand t[22]..t[0] and makes it 0t[22]...t[1], so the significand is (approximately) 1.0t which represents 1+t/2. If e is odd, say, e = 2*p+1, then sqrt(x) = sqrt(2(1.t))*2^p. The number 2(1.t) represents 2+2*t and sqrt(2+2*t) is approximately 3/2+t/2. The biased exponents is even, so the subtraction of 1 produces an odd number and bit 23 is a 1. The right-shift takes trailing significand t[22]...t[0] and makes it 1t[22]...t[1], so the significand is (approximately) 1.1t which represents 3/2+t/2. If instead you are referring to the inverse square root, the Wikipedia page for the inverse square root has a history of the algorithm that is more detailed than on the square root page (and the two pages are not quite in agreement).[[User:Daveeberly|Daveeberly]] ([[User talk:Daveeberly|talk]]) 06:15, 14 July 2010 (UTC)
== Digit by digit method is not fully explained. ==
Line 159 ⟶ 161:
:We do have an article about [[CORDIC]], which mentions computing square roots but does not give further details. I added a sentence to this article with a link to CORDIC. I don't have an idea whether CORDIC is still used (or was ever used) to compute square roots, but it would be good to have some more details. -- [[User:Jitse Niesen|Jitse Niesen]] ([[User talk:Jitse Niesen|talk]]) 14:42, 8 December 2008 (UTC)
== About A two-variable iterative method ==
It is not clear where the pair of equations come from, although reverse engineering them is not too difficult. However, it is simple enough to show that a[n+1] = (3*S*a[n] - a[n]^3)/(2*S), which makes the algorithm equivalent to applying Newton's method to F(y) = 1/y^2 - 1/S (the a[i] are the iterates with a[0] = S).[[User:Daveeberly|Daveeberly]] ([[User talk:Daveeberly|talk]]) 06:15, 14 July 2010 (UTC)
| |||