The Tor Browser / file comparison
comparison: security/nss/lib/freebl/mpi/doc/sqrt.txt
security/nss/lib/freebl/mpi/doc/sqrt.txt
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:568efbb72770 |
|---|---|
| 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/. |
