michael@0: Square Root
michael@0: 
michael@0: A simple iterative algorithm is used to compute the greatest integer
michael@0: less than or equal to the square root.  Essentially, this is Newton's
michael@0: linear approximation, computed by finding successive values of the
michael@0: equation:
michael@0: 
michael@0: 		    x[k]^2 - V
michael@0: x[k+1]	 =  x[k] - ------------
michael@0: 	             2 x[k]
michael@0: 
michael@0: ...where V is the value for which the square root is being sought.  In
michael@0: essence, what is happening here is that we guess a value for the
michael@0: square root, then figure out how far off we were by squaring our guess
michael@0: and subtracting the target.  Using this value, we compute a linear
michael@0: approximation for the error, and adjust the "guess".  We keep doing
michael@0: this until the precision gets low enough that the above equation
michael@0: yields a quotient of zero.  At this point, our last guess is one
michael@0: greater than the square root we're seeking.
michael@0: 
michael@0: The initial guess is computed by dividing V by 4, which is a heuristic
michael@0: I have found to be fairly good on average.  This also has the
michael@0: advantage of being very easy to compute efficiently, even for large
michael@0: values.
michael@0: 
michael@0: So, the resulting algorithm works as follows:
michael@0: 
michael@0:     x = V / 4   /* compute initial guess */
michael@0:     
michael@0:     loop
michael@0: 	t = (x * x) - V   /* Compute absolute error  */
michael@0: 	u = 2 * x         /* Adjust by tangent slope */
michael@0: 	t = t / u
michael@0: 
michael@0: 	/* Loop is done if error is zero */
michael@0: 	if(t == 0)
michael@0: 	    break
michael@0: 
michael@0: 	/* Adjust guess by error term    */
michael@0: 	x = x - t
michael@0:     end
michael@0: 
michael@0:     x = x - 1
michael@0: 
michael@0: The result of the computation is the value of x.
michael@0: 
michael@0: ------------------------------------------------------------------
michael@0:  This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  # License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  # file, You can obtain one at http://mozilla.org/MPL/2.0/.