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