Square Root
Square root also uses NR calculation of a quadratically converging
sequence. The sequence converges to the reciprocal of the
square root, which is then multiplied by the value the
square root is sought for:
|
|
sqrt(A) = A × 1/sqrt(A)
|
The reciprocal of the square root, u = 1/sqrt(A), is calculated:
|
WideFloat u,v,s,r;
double first_estimate;
v=A;
first_estimate=1.0/sqrt(double(v));
u=first_estimate;
r=u*u; s=r*v; s=3-s;
s /= 2; //right shift 1 bit
u=u*s;
r=u*u; s=r*v; s=3-s;
s /= 2; //right shift 1 bit
u=u*s;
|
|
The square root becomes: sqrt( A ) = A × u.
Note: Division by 2 is accomplished by
right shifting the significand one bit
and renormalizing if necessary.
Renormalizing consists of shifting the digit packets until one
non-zero digit packet is to the left of the radix point,
then adjusting the exponent by the number of digit packet
positions shifted.
|
|
1.
|
Muller, J.M., 2006,
Elementary Functions: Algorithms and Implementation
2nd ed.,
p. 93.
|
|
|
|
2.
|
Parker, A., 1993,
Algorithms and Data Structures in C++,
p. 241.
|
|
|
|
3.
|
Press, W.H., Teukolsky, S.A., Vetterling, W.T., and Flannery, B.P., 2002,
Numerical Recipes in C++
2nd ed., p. 922.
|
|
|
|
4.
|
Abramowitz, M., and Stegun, I.A., 1972,
Handbook of Mathematical Functions,
p. 15,
eq. 3.6.12.
|
