diff options
Diffstat (limited to 'libm/e_sqrt.c')
| -rw-r--r-- | libm/e_sqrt.c | 94 |
1 files changed, 47 insertions, 47 deletions
diff --git a/libm/e_sqrt.c b/libm/e_sqrt.c index 15fba001d..fae52c842 100644 --- a/libm/e_sqrt.c +++ b/libm/e_sqrt.c @@ -5,7 +5,7 @@ * * Developed at SunPro, a Sun Microsystems, Inc. business. * Permission to use, copy, modify, and distribute this - * software is freely granted, provided that this notice + * software is freely granted, provided that this notice * is preserved. * ==================================================== */ @@ -19,10 +19,10 @@ static char rcsid[] = "$NetBSD: e_sqrt.c,v 1.8 1995/05/10 20:46:17 jtc Exp $"; * ------------------------------------------ * | Use the hardware sqrt if you have one | * ------------------------------------------ - * Method: - * Bit by bit method using integer arithmetic. (Slow, but portable) + * Method: + * Bit by bit method using integer arithmetic. (Slow, but portable) * 1. Normalization - * Scale x to y in [1,4) with even powers of 2: + * Scale x to y in [1,4) with even powers of 2: * find an integer k such that 1 <= (y=x*2^(2k)) < 4, then * sqrt(x) = 2^k * sqrt(y) * 2. Bit by bit computation @@ -31,9 +31,9 @@ static char rcsid[] = "$NetBSD: e_sqrt.c,v 1.8 1995/05/10 20:46:17 jtc Exp $"; * i+1 2 * s = 2*q , and y = 2 * ( y - q ). (1) * i i i i - * - * To compute q from q , one checks whether - * i+1 i + * + * To compute q from q , one checks whether + * i+1 i * * -(i+1) 2 * (q + 2 ) <= y. (2) @@ -43,12 +43,12 @@ static char rcsid[] = "$NetBSD: e_sqrt.c,v 1.8 1995/05/10 20:46:17 jtc Exp $"; * i+1 i i+1 i * * With some algebric manipulation, it is not difficult to see - * that (2) is equivalent to + * that (2) is equivalent to * -(i+1) * s + 2 <= y (3) * i i * - * The advantage of (3) is that s and y can be computed by + * The advantage of (3) is that s and y can be computed by * i i * the following recurrence formula: * if (3) is false @@ -60,10 +60,10 @@ static char rcsid[] = "$NetBSD: e_sqrt.c,v 1.8 1995/05/10 20:46:17 jtc Exp $"; * -i -(i+1) * s = s + 2 , y = y - s - 2 (5) * i+1 i i+1 i i - * - * One may easily use induction to prove (4) and (5). + * + * One may easily use induction to prove (4) and (5). * Note. Since the left hand side of (3) contain only i+2 bits, - * it does not necessary to do a full (53-bit) comparison + * it does not necessary to do a full (53-bit) comparison * in (3). * 3. Final rounding * After generating the 53 bits result, we compute one more bit. @@ -73,7 +73,7 @@ static char rcsid[] = "$NetBSD: e_sqrt.c,v 1.8 1995/05/10 20:46:17 jtc Exp $"; * The rounding mode can be detected by checking whether * huge + tiny is equal to huge, and whether huge - tiny is * equal to huge for some floating point number "huge" and "tiny". - * + * * Special cases: * sqrt(+-0) = +-0 ... exact * sqrt(inf) = inf @@ -101,17 +101,17 @@ static double one = 1.0, tiny=1.0e-300; #endif { double z; - int32_t sign = (int)0x80000000; + int32_t sign = (int)0x80000000; int32_t ix0,s0,q,m,t,i; u_int32_t r,t1,s1,ix1,q1; EXTRACT_WORDS(ix0,ix1,x); /* take care of Inf and NaN */ - if((ix0&0x7ff00000)==0x7ff00000) { + if((ix0&0x7ff00000)==0x7ff00000) { return x*x+x; /* sqrt(NaN)=NaN, sqrt(+inf)=+inf sqrt(-inf)=sNaN */ - } + } /* take care of zero */ if(ix0<=0) { if(((ix0&(~sign))|ix1)==0) return x;/* sqrt(+-0) = +-0 */ @@ -145,12 +145,12 @@ static double one = 1.0, tiny=1.0e-300; r = 0x00200000; /* r = moving bit from right to left */ while(r!=0) { - t = s0+r; - if(t<=ix0) { - s0 = t+r; - ix0 -= t; - q += r; - } + t = s0+r; + if(t<=ix0) { + s0 = t+r; + ix0 -= t; + q += r; + } ix0 += ix0 + ((ix1&sign)>>31); ix1 += ix1; r>>=1; @@ -158,9 +158,9 @@ static double one = 1.0, tiny=1.0e-300; r = sign; while(r!=0) { - t1 = s1+r; + t1 = s1+r; t = s0; - if((t<ix0)||((t==ix0)&&(t1<=ix1))) { + if((t<ix0)||((t==ix0)&&(t1<=ix1))) { s1 = t1+r; if(((t1&sign)==sign)&&(s1&sign)==0) s0 += 1; ix0 -= t; @@ -181,7 +181,7 @@ static double one = 1.0, tiny=1.0e-300; if (q1==(u_int32_t)0xffffffff) { q1=0; q += 1;} else if (z>one) { if (q1==(u_int32_t)0xfffffffe) q+=1; - q1+=2; + q1+=2; } else q1 += (q1&1); } @@ -197,18 +197,18 @@ static double one = 1.0, tiny=1.0e-300; /* Other methods (use floating-point arithmetic) ------------- -(This is a copy of a drafted paper by Prof W. Kahan +(This is a copy of a drafted paper by Prof W. Kahan and K.C. Ng, written in May, 1986) - Two algorithms are given here to implement sqrt(x) + Two algorithms are given here to implement sqrt(x) (IEEE double precision arithmetic) in software. Both supply sqrt(x) correctly rounded. The first algorithm (in Section A) uses newton iterations and involves four divisions. The second one uses reciproot iterations to avoid division, but requires more multiplications. Both algorithms need the ability - to chop results of arithmetic operations instead of round them, + to chop results of arithmetic operations instead of round them, and the INEXACT flag to indicate when an arithmetic operation - is executed exactly with no roundoff error, all part of the + is executed exactly with no roundoff error, all part of the standard (IEEE 754-1985). The ability to perform shift, add, subtract and logical AND operations upon 32-bit words is needed too, though not part of the standard. @@ -218,7 +218,7 @@ A. sqrt(x) by Newton Iteration (1) Initial approximation Let x0 and x1 be the leading and the trailing 32-bit words of - a floating point number x (in IEEE double format) respectively + a floating point number x (in IEEE double format) respectively 1 11 52 ...widths ------------------------------------------------------ @@ -226,7 +226,7 @@ A. sqrt(x) by Newton Iteration ------------------------------------------------------ msb lsb msb lsb ...order - + ------------------------ ------------------------ x0: |s| e | f1 | x1: | f2 | ------------------------ ------------------------ @@ -251,7 +251,7 @@ A. sqrt(x) by Newton Iteration (2) Iterative refinement - Apply Heron's rule three times to y, we have y approximates + Apply Heron's rule three times to y, we have y approximates sqrt(x) to within 1 ulp (Unit in the Last Place): y := (y+x/y)/2 ... almost 17 sig. bits @@ -276,12 +276,12 @@ A. sqrt(x) by Newton Iteration it requires more multiplications and additions. Also x must be scaled in advance to avoid spurious overflow in evaluating the expression 3y*y+x. Hence it is not recommended uless division - is slow. If division is very slow, then one should use the + is slow. If division is very slow, then one should use the reciproot algorithm given in section B. (3) Final adjustment - By twiddling y's last bit it is possible to force y to be + By twiddling y's last bit it is possible to force y to be correctly rounded according to the prevailing rounding mode as follows. Let r and i be copies of the rounding mode and inexact flag before entering the square root program. Also we @@ -312,7 +312,7 @@ A. sqrt(x) by Newton Iteration I := i; ... restore inexact flag R := r; ... restore rounded mode return sqrt(x):=y. - + (4) Special cases Square root of +inf, +-0, or NaN is itself; @@ -331,7 +331,7 @@ B. sqrt(x) by Reciproot Iteration k := 0x5fe80000 - (x0>>1); y0:= k - T2[63&(k>>14)]. ... y ~ 1/sqrt(x) to 7.8 bits - Here k is a 32-bit integer and T2[] is an integer array + Here k is a 32-bit integer and T2[] is an integer array containing correction terms. Now magically the floating value of y (y's leading 32-bit word is y0, the value of its trailing word y1 is set to zero) approximates 1/sqrt(x) @@ -352,9 +352,9 @@ B. sqrt(x) by Reciproot Iteration Apply Reciproot iteration three times to y and multiply the result by x to get an approximation z that matches sqrt(x) - to about 1 ulp. To be exact, we will have + to about 1 ulp. To be exact, we will have -1ulp < sqrt(x)-z<1.0625ulp. - + ... set rounding mode to Round-to-nearest y := y*(1.5-0.5*x*y*y) ... almost 15 sig. bits to 1/sqrt(x) y := y*((1.5-2^-30)+0.5*x*y*y)... about 29 sig. bits to 1/sqrt(x) @@ -363,14 +363,14 @@ B. sqrt(x) by Reciproot Iteration z := z + 0.5*z*(1-z*y) ... about 1 ulp to sqrt(x) Remark 2. The constant 1.5-2^-30 is chosen to bias the error so that - (a) the term z*y in the final iteration is always less than 1; + (a) the term z*y in the final iteration is always less than 1; (b) the error in the final result is biased upward so that -1 ulp < sqrt(x) - z < 1.0625 ulp instead of |sqrt(x)-z|<1.03125ulp. (3) Final adjustment - By twiddling y's last bit it is possible to force y to be + By twiddling y's last bit it is possible to force y to be correctly rounded according to the prevailing rounding mode as follows. Let r and i be copies of the rounding mode and inexact flag before entering the square root program. Also we @@ -410,27 +410,27 @@ B. sqrt(x) by Reciproot Iteration I := 1; ... Raise Inexact flag: z is not exact else { j := 1 - [(x0>>20)&1] ... j = logb(x) mod 2 - k := z1 >> 26; ... get z's 25-th and 26-th + k := z1 >> 26; ... get z's 25-th and 26-th fraction bits I := i or (k&j) or ((k&(j+j+1))!=(x1&3)); } R:= r ... restore rounded mode return sqrt(x):=z. - If multiplication is cheaper then the foregoing red tape, the + If multiplication is cheaper then the foregoing red tape, the Inexact flag can be evaluated by I := i; I := (z*z!=x) or I. - Note that z*z can overwrite I; this value must be sensed if it is + Note that z*z can overwrite I; this value must be sensed if it is True. Remark 4. If z*z = x exactly, then bit 25 to bit 0 of z1 must be zero. -------------------- - z1: | f2 | + z1: | f2 | -------------------- bit 31 bit 0 @@ -447,7 +447,7 @@ B. sqrt(x) by Reciproot Iteration 11 01 even ------------------------------------------------- - (4) Special cases (see (4) of Section A). - + (4) Special cases (see (4) of Section A). + */ - + |