sqrt.txt (1692B)
1 Square Root 2 3 A simple iterative algorithm is used to compute the greatest integer 4 less than or equal to the square root. Essentially, this is Newton's 5 linear approximation, computed by finding successive values of the 6 equation: 7 8 x[k]^2 - V 9 x[k+1] = x[k] - ------------ 10 2 x[k] 11 12 ...where V is the value for which the square root is being sought. In 13 essence, what is happening here is that we guess a value for the 14 square root, then figure out how far off we were by squaring our guess 15 and subtracting the target. Using this value, we compute a linear 16 approximation for the error, and adjust the "guess". We keep doing 17 this until the precision gets low enough that the above equation 18 yields a quotient of zero. At this point, our last guess is one 19 greater than the square root we're seeking. 20 21 The initial guess is computed by dividing V by 4, which is a heuristic 22 I have found to be fairly good on average. This also has the 23 advantage of being very easy to compute efficiently, even for large 24 values. 25 26 So, the resulting algorithm works as follows: 27 28 x = V / 4 /* compute initial guess */ 29 30 loop 31 t = (x * x) - V /* Compute absolute error */ 32 u = 2 * x /* Adjust by tangent slope */ 33 t = t / u 34 35 /* Loop is done if error is zero */ 36 if(t == 0) 37 break 38 39 /* Adjust guess by error term */ 40 x = x - t 41 end 42 43 x = x - 1 44 45 The result of the computation is the value of x. 46 47 ------------------------------------------------------------------ 48 This Source Code Form is subject to the terms of the Mozilla Public 49 # License, v. 2.0. If a copy of the MPL was not distributed with this 50 # file, You can obtain one at http://mozilla.org/MPL/2.0/.