1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/mpi/doc/sqrt.txt Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,50 @@
1.4 +Square Root
1.5 +
1.6 +A simple iterative algorithm is used to compute the greatest integer
1.7 +less than or equal to the square root. Essentially, this is Newton's
1.8 +linear approximation, computed by finding successive values of the
1.9 +equation:
1.10 +
1.11 + x[k]^2 - V
1.12 +x[k+1] = x[k] - ------------
1.13 + 2 x[k]
1.14 +
1.15 +...where V is the value for which the square root is being sought. In
1.16 +essence, what is happening here is that we guess a value for the
1.17 +square root, then figure out how far off we were by squaring our guess
1.18 +and subtracting the target. Using this value, we compute a linear
1.19 +approximation for the error, and adjust the "guess". We keep doing
1.20 +this until the precision gets low enough that the above equation
1.21 +yields a quotient of zero. At this point, our last guess is one
1.22 +greater than the square root we're seeking.
1.23 +
1.24 +The initial guess is computed by dividing V by 4, which is a heuristic
1.25 +I have found to be fairly good on average. This also has the
1.26 +advantage of being very easy to compute efficiently, even for large
1.27 +values.
1.28 +
1.29 +So, the resulting algorithm works as follows:
1.30 +
1.31 + x = V / 4 /* compute initial guess */
1.32 +
1.33 + loop
1.34 + t = (x * x) - V /* Compute absolute error */
1.35 + u = 2 * x /* Adjust by tangent slope */
1.36 + t = t / u
1.37 +
1.38 + /* Loop is done if error is zero */
1.39 + if(t == 0)
1.40 + break
1.41 +
1.42 + /* Adjust guess by error term */
1.43 + x = x - t
1.44 + end
1.45 +
1.46 + x = x - 1
1.47 +
1.48 +The result of the computation is the value of x.
1.49 +
1.50 +------------------------------------------------------------------
1.51 + This Source Code Form is subject to the terms of the Mozilla Public
1.52 + # License, v. 2.0. If a copy of the MPL was not distributed with this
1.53 + # file, You can obtain one at http://mozilla.org/MPL/2.0/.
