security/nss/lib/freebl/mpi/doc/sqrt.txt
author Ryan VanderMeulen <ryanvm@gmail.com>
Wed, 01 May 2013 16:05:10 -0400
changeset 130538 05275490b9c18457c4459057a117afd6d6c9226d
parent 130535 0314d200873a8962e8556a656bbf9e4b26e23cfc
child 130699 c6f5c1bbcf761369c0d51f85ba1bb110f2f40fd8
permissions -rw-r--r--
Backed out changeset 0314d200873a (bug 858231) for Windows build bustage. CLOSED TREE

Square Root

A simple iterative algorithm is used to compute the greatest integer
less than or equal to the square root.  Essentially, this is Newton's
linear approximation, computed by finding successive values of the
equation:

		    x[k]^2 - V
x[k+1]	 =  x[k] - ------------
	             2 x[k]

...where V is the value for which the square root is being sought.  In
essence, what is happening here is that we guess a value for the
square root, then figure out how far off we were by squaring our guess
and subtracting the target.  Using this value, we compute a linear
approximation for the error, and adjust the "guess".  We keep doing
this until the precision gets low enough that the above equation
yields a quotient of zero.  At this point, our last guess is one
greater than the square root we're seeking.

The initial guess is computed by dividing V by 4, which is a heuristic
I have found to be fairly good on average.  This also has the
advantage of being very easy to compute efficiently, even for large
values.

So, the resulting algorithm works as follows:

    x = V / 4   /* compute initial guess */
    
    loop
	t = (x * x) - V   /* Compute absolute error  */
	u = 2 * x         /* Adjust by tangent slope */
	t = t / u

	/* Loop is done if error is zero */
	if(t == 0)
	    break

	/* Adjust guess by error term    */
	x = x - t
    end

    x = x - 1

The result of the computation is the value of x.

------------------------------------------------------------------
 This Source Code Form is subject to the terms of the Mozilla Public
 # License, v. 2.0. If a copy of the MPL was not distributed with this
 # file, You can obtain one at http://mozilla.org/MPL/2.0/.

$Id$