summaryrefslogtreecommitdiff
path: root/sysdeps/libm-ieee754/e_sqrt.c
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>1996-12-20 01:39:50 +0000
committerUlrich Drepper <drepper@redhat.com>1996-12-20 01:39:50 +0000
commit6d52618b15cbe25ed4822ac51321db292f28ccda (patch)
treebafef072c0f5cb67c09d7c1789888d4310ac568f /sysdeps/libm-ieee754/e_sqrt.c
parent10dc2a90b7f86d9bc1be9d1b9305a781882f7ac5 (diff)
Update from main archive 961219cvs/libc-961220
Thu Dec 19 23:28:33 1996 Ulrich Drepper <drepper@cygnus.com> * resolv/resolv.h: Update from BIND 4.9.5-P1. * resolv/res_comp.c: Likewise. * resolv/res_debug.c: Likewise. * resolv/Banner: Update version number. Thu Dec 19 20:58:53 1996 Ulrich Drepper <drepper@cygnus.com> * elf/dlfcn.h: Add extern "C" wrapper. * io/utime.h: Don't define NULL since this isn't allowed in POSIX. * io/sys/stat.h: Declare `lstat' only if __USE_BSD || __USE_XOPEN_EXTENDED. * locale/locale.h: Define NULL. * math/math.c: Don't include <errno.h> to define math errors. * stdlib/stdlib.h: Likewise. * posix/unistd.h: Don't declare environ. * posix/sys/utsname.h (struct utsname): Declare member domainname as __domainname is !__USE_GNU. * signal/signal.h: Declare size_t only if __USE_BSD || __USE_XOPEN_EXTENDED. * stdio/stdio.h: Don't declare cuserid when __USE_POSIX, but instead when __USE_XOPEN. * string/string.h: Define strndup only if __USE_GNU. * sysdeps/unix/sysv/linux/clock.c: New file. * sysdeps/unix/sysv/linux/timebits.h: Define CLOCKS_PER_SEC as 1000000 per X/Open standard. * features.h: Add code to recognize _POSIX_C_SOURCE value 199309. Define __USE_POSIX199309. * posix/unistd.h: Declare fdatasync only if __USE_POSIX199309. * time/time.c: Declare nanosleep only if __USE_POSIX199309. Patches by Rüdiger Helsch <rh@unifix.de>. * locale/locale.h: Add declaration of newlocale and freelocale. * new-malloc/Makefile (distibute): Add mtrace.awk. (dist-routines): Add mcheck and mtrace. (install-lib, non-lib.a): Define as libmcheck.a. * new-malloc/malloc.h: Add declaration of __malloc_initialized. * new-malloc/mcheck.c: New file. * new-malloc/mcheck.h: New file. * new-malloc/mtrace.c: New file. * new-malloc/mtrace.awk: New file. * posix/unistd.h: Correct prototype for usleep. * sysdeps/unix/bsd/usleep.c: De-ANSI-declfy. Correct return type. * sysdeps/unix/sysv/linux/usleep.c: Real implementation based on nanosleep. * signal/signal.h: Change protoype of __sigpause to take two arguments. Remove prototype for sigpause. Add two different macros named sigpause selected when __USE_BSD or __USE_XOPEN are defined. This is necessary since the old BSD definition of theis function collides with the X/Open definition. * sysdeps/posix/sigpause.c: Change function definition to also fit X/Open definition. * sysdeps/libm-i387/e_exp.S: Make sure stack is empty when the function is left. * sysdeps/libm-i387/e_expl.S: Likewise. Patch by HJ Lu. 1996-12-17 Paul Eggert <eggert@twinsun.com> * many, many files: Spelling corrections. * catgets/catgetsinfo.h (mmapped): Renamed from mmaped (in struct catalog_info.status). * mach/err_kern.sub (err_codes_unix), string/stratcliff.c (main): Fix spelling in message. * po/libc.pot: Fix spelling in message for `zic'; this anticipates a fix in the tzcode distribution. Wed Dec 18 15:48:02 1996 Ulrich Drepper <drepper@cygnus.com> * time/strftime.c: Implement ^ flag to cause output be converted to use upper case characters. * time/zic.c: Update from ADO tzcode1996n. Wed Dec 18 14:29:24 1996 Erik Naggum <erik@naggum.no> * time/strftime.c (add): Don't change global `i' until all is over. Define NULL is not already defined. Tue Dec 17 09:49:03 1996 Andreas Schwab <schwab@issan.informatik.uni-dortmund.de> * libio/iovsprintf.c (_IO_vsprintf): Change `&sf' to `&sf._sbf._f' to avoid the need for a cast. * libio/iovsscanf.c (_IO_vsscanf): Likewise. * sunrpc/rpc/xdr.h: Add prototype for xdr_free.
Diffstat (limited to 'sysdeps/libm-ieee754/e_sqrt.c')
-rw-r--r--sysdeps/libm-ieee754/e_sqrt.c95
1 files changed, 47 insertions, 48 deletions
diff --git a/sysdeps/libm-ieee754/e_sqrt.c b/sysdeps/libm-ieee754/e_sqrt.c
index 15fba001d3..67da5455f9 100644
--- a/sysdeps/libm-ieee754/e_sqrt.c
+++ b/sysdeps/libm-ieee754/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)
@@ -42,13 +42,13 @@ static char rcsid[] = "$NetBSD: e_sqrt.c,v 1.8 1995/05/10 20:46:17 jtc Exp $";
* If (2) is false, then q = q ; otherwise q = q + 2 .
* i+1 i i+1 i
*
- * With some algebric manipulation, it is not difficult to see
- * that (2) is equivalent to
+ * With some algebraic manipulation, it is not difficult to see
+ * 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,6 @@ 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).
+
*/
-