lib/libm/src/e_sqrt.c

   1
   2 /* @(#)e_sqrt.c 1.3 95/01/18 */
   3 /*
   4  * ====================================================
   5  * Copyright (C) 1993 by Sun Microsystems, Inc. All rights reserved.
   6  *
   7  * Developed at SunSoft, a Sun Microsystems, Inc. business.
   8  * Permission to use, copy, modify, and distribute this
   9  * software is freely granted, provided that this notice
  10  * is preserved.
  11  * ====================================================
  12  */
  13
  14
  15 /* __ieee754_sqrt(x)
  16  * Return correctly rounded sqrt.
  17  *           ------------------------------------------
  18  *           |  Use the hardware sqrt if you have one |
  19  *           ------------------------------------------
  20  * Method:
  21  *   Bit by bit method using integer arithmetic. (Slow, but portable)
  22  *   1. Normalization
  23  *      Scale x to y in [1,4) with even powers of 2:
  24  *      find an integer k such that  1 <= (y=x*2^(2k)) < 4, then
  25  *              sqrt(x) = 2^k * sqrt(y)
  26  *   2. Bit by bit computation
  27  *      Let q  = sqrt(y) truncated to i bit after binary point (q = 1),
  28  *           i                                                   0
  29  *                                     i+1         2
  30  *          s  = 2*q , and      y  =  2   * ( y - q  ).         (1)
  31  *           i      i            i                 i
  32  *
  33  *      To compute q    from q , one checks whether
  34  *                  i+1       i
  35  *
  36  *                            -(i+1) 2
  37  *                      (q + 2      ) <= y.                     (2)
  38  *                        i
  39  *                                                            -(i+1)
  40  *      If (2) is false, then q   = q ; otherwise q   = q  + 2      .
  41  *                             i+1   i             i+1   i
  42  *
  43  *      With some algebric manipulation, it is not difficult to see
  44  *      that (2) is equivalent to
  45  *                             -(i+1)
  46  *                      s  +  2       <= y                      (3)
  47  *                       i                i
  48  *
  49  *      The advantage of (3) is that s  and y  can be computed by
  50  *                                    i      i
  51  *      the following recurrence formula:
  52  *          if (3) is false
  53  *
  54  *          s     =  s  ,       y    = y   ;                    (4)
  55  *           i+1      i          i+1    i
  56  *
  57  *          otherwise,
  58  *                         -i                     -(i+1)
  59  *          s     =  s  + 2  ,  y    = y  -  s  - 2             (5)
  60  *           i+1      i          i+1    i     i
  61  *
  62  *      One may easily use induction to prove (4) and (5).
  63  *      Note. Since the left hand side of (3) contain only i+2 bits,
  64  *            it does not necessary to do a full (53-bit) comparison
  65  *            in (3).
  66  *   3. Final rounding
  67  *      After generating the 53 bits result, we compute one more bit.
  68  *      Together with the remainder, we can decide whether the
  69  *      result is exact, bigger than 1/2ulp, or less than 1/2ulp
  70  *      (it will never equal to 1/2ulp).
  71  *      The rounding mode can be detected by checking whether
  72  *      huge + tiny is equal to huge, and whether huge - tiny is
  73  *      equal to huge for some floating point number "huge" and "tiny".
  74  *
  75  * Special cases:
  76  *      sqrt(+-0) = +-0         ... exact
  77  *      sqrt(inf) = inf
  78  *      sqrt(-ve) = NaN         ... with invalid signal
  79  *      sqrt(NaN) = NaN         ... with invalid signal for signaling NaN
  80  *
  81  * Other methods : see the appended file at the end of the program below.
  82  *---------------
  83  */
  84
  85 #include <float.h>
  86
  87 #include "math.h"
  88 #include "math_private.h"
  89
  90 static  const double    one     = 1.0, tiny=1.0e-300;
  91
  92 double
  93 __ieee754_sqrt(double x)
  94 {
  95         double z;
  96         int32_t sign = (int)0x80000000;
  97         int32_t ix0,s0,q,m,t,i;
  98         u_int32_t r,t1,s1,ix1,q1;
  99
 100         EXTRACT_WORDS(ix0,ix1,x);
 101
 102     /* take care of Inf and NaN */
 103         if((ix0&0x7ff00000)==0x7ff00000) {
 104             return x*x+x;               /* sqrt(NaN)=NaN, sqrt(+inf)=+inf
 105                                            sqrt(-inf)=sNaN */
 106         }
 107     /* take care of zero */
 108         if(ix0<=0) {
 109             if(((ix0&(~sign))|ix1)==0) return x;/* sqrt(+-0) = +-0 */
 110             else if(ix0<0)
 111                 return (x-x)/(x-x);             /* sqrt(-ve) = sNaN */
 112         }
 113     /* normalize x */
 114         m = (ix0>>20);
 115         if(m==0) {                              /* subnormal x */
 116             while(ix0==0) {
 117                 m -= 21;
 118                 ix0 |= (ix1>>11); ix1 <<= 21;
 119             }
 120             for(i=0;(ix0&0x00100000)==0;i++) ix0<<=1;
 121             m -= i-1;
 122             ix0 |= (ix1>>(32-i));
 123             ix1 <<= i;
 124         }
 125         m -= 1023;      /* unbias exponent */
 126         ix0 = (ix0&0x000fffff)|0x00100000;
 127         if(m&1){        /* odd m, double x to make it even */
 128             ix0 += ix0 + ((ix1&sign)>>31);
 129             ix1 += ix1;
 130         }
 131         m >>= 1;        /* m = [m/2] */
 132
 133     /* generate sqrt(x) bit by bit */
 134         ix0 += ix0 + ((ix1&sign)>>31);
 135         ix1 += ix1;
 136         q = q1 = s0 = s1 = 0;   /* [q,q1] = sqrt(x) */
 137         r = 0x00200000;         /* r = moving bit from right to left */
 138
 139         while(r!=0) {
 140             t = s0+r;
 141             if(t<=ix0) {
 142                 s0   = t+r;
 143                 ix0 -= t;
 144                 q   += r;
 145             }
 146             ix0 += ix0 + ((ix1&sign)>>31);
 147             ix1 += ix1;
 148             r>>=1;
 149         }
 150
 151         r = sign;
 152         while(r!=0) {
 153             t1 = s1+r;
 154             t  = s0;
 155             if((t<ix0)||((t==ix0)&&(t1<=ix1))) {
 156                 s1  = t1+r;
 157                 if(((t1&sign)==sign)&&(s1&sign)==0) s0 += 1;
 158                 ix0 -= t;
 159                 if (ix1 < t1) ix0 -= 1;
 160                 ix1 -= t1;
 161                 q1  += r;
 162             }
 163             ix0 += ix0 + ((ix1&sign)>>31);
 164             ix1 += ix1;
 165             r>>=1;
 166         }
 167
 168     /* use floating add to find out rounding direction */
 169         if((ix0|ix1)!=0) {
 170             z = one-tiny; /* trigger inexact flag */
 171             if (z>=one) {
 172                 z = one+tiny;
 173                 if (q1==(u_int32_t)0xffffffff) { q1=0; q += 1;}
 174                 else if (z>one) {
 175                     if (q1==(u_int32_t)0xfffffffe) q+=1;
 176                     q1+=2;
 177                 } else
 178                     q1 += (q1&1);
 179             }
 180         }
 181         ix0 = (q>>1)+0x3fe00000;
 182         ix1 =  q1>>1;
 183         if ((q&1)==1) ix1 |= sign;
 184         ix0 += (m <<20);
 185         INSERT_WORDS(z,ix0,ix1);
 186         return z;
 187 }
 188
 189 #if (LDBL_MANT_DIG == 53)
 190 __weak_reference(sqrt, sqrtl);
 191 #endif
 192
 193 /*
 194 Other methods  (use floating-point arithmetic)
 195 -------------
 196 (This is a copy of a drafted paper by Prof W. Kahan
 197 and K.C. Ng, written in May, 1986)
 198
 199         Two algorithms are given here to implement sqrt(x)
 200         (IEEE double precision arithmetic) in software.
 201         Both supply sqrt(x) correctly rounded. The first algorithm (in
 202         Section A) uses newton iterations and involves four divisions.
 203         The second one uses reciproot iterations to avoid division, but
 204         requires more multiplications. Both algorithms need the ability
 205         to chop results of arithmetic operations instead of round them,
 206         and the INEXACT flag to indicate when an arithmetic operation
 207         is executed exactly with no roundoff error, all part of the
 208         standard (IEEE 754-1985). The ability to perform shift, add,
 209         subtract and logical AND operations upon 32-bit words is needed
 210         too, though not part of the standard.
 211
 212 A.  sqrt(x) by Newton Iteration
 213
 214    (1)  Initial approximation
 215
 216         Let x0 and x1 be the leading and the trailing 32-bit words of
 217         a floating point number x (in IEEE double format) respectively
 218
 219             1    11                  52                           ...widths
 220            ------------------------------------------------------
 221         x: |s|    e     |             f                         |
 222            ------------------------------------------------------
 223               msb    lsb  msb                                 lsb ...order
 224
 225
 226              ------------------------        ------------------------
 227         x0:  |s|   e    |    f1     |    x1: |          f2           |
 228              ------------------------        ------------------------
 229
 230         By performing shifts and subtracts on x0 and x1 (both regarded
 231         as integers), we obtain an 8-bit approximation of sqrt(x) as
 232         follows.
 233
 234                 k  := (x0>>1) + 0x1ff80000;
 235                 y0 := k - T1[31&(k>>15)].       ... y ~ sqrt(x) to 8 bits
 236         Here k is a 32-bit integer and T1[] is an integer array containing
 237         correction terms. Now magically the floating value of y (y's
 238         leading 32-bit word is y0, the value of its trailing word is 0)
 239         approximates sqrt(x) to almost 8-bit.
 240
 241         Value of T1:
 242         static int T1[32]= {
 243         0,      1024,   3062,   5746,   9193,   13348,  18162,  23592,
 244         29598,  36145,  43202,  50740,  58733,  67158,  75992,  85215,
 245         83599,  71378,  60428,  50647,  41945,  34246,  27478,  21581,
 246         16499,  12183,  8588,   5674,   3403,   1742,   661,    130,};
 247
 248     (2) Iterative refinement
 249
 250         Apply Heron's rule three times to y, we have y approximates
 251         sqrt(x) to within 1 ulp (Unit in the Last Place):
 252
 253                 y := (y+x/y)/2          ... almost 17 sig. bits
 254                 y := (y+x/y)/2          ... almost 35 sig. bits
 255                 y := y-(y-x/y)/2        ... within 1 ulp
 256
 257
 258         Remark 1.
 259             Another way to improve y to within 1 ulp is:
 260
 261                 y := (y+x/y)            ... almost 17 sig. bits to 2*sqrt(x)
 262                 y := y - 0x00100006     ... almost 18 sig. bits to sqrt(x)
 263
 264                                 2
 265                             (x-y )*y
 266                 y := y + 2* ----------  ...within 1 ulp
 267                                2
 268                              3y  + x
 269
 270
 271         This formula has one division fewer than the one above; however,
 272         it requires more multiplications and additions. Also x must be
 273         scaled in advance to avoid spurious overflow in evaluating the
 274         expression 3y*y+x. Hence it is not recommended uless division
 275         is slow. If division is very slow, then one should use the
 276         reciproot algorithm given in section B.
 277
 278     (3) Final adjustment
 279
 280         By twiddling y's last bit it is possible to force y to be
 281         correctly rounded according to the prevailing rounding mode
 282         as follows. Let r and i be copies of the rounding mode and
 283         inexact flag before entering the square root program. Also we
 284         use the expression y+-ulp for the next representable floating
 285         numbers (up and down) of y. Note that y+-ulp = either fixed
 286         point y+-1, or multiply y by nextafter(1,+-inf) in chopped
 287         mode.
 288
 289                 I := FALSE;     ... reset INEXACT flag I
 290                 R := RZ;        ... set rounding mode to round-toward-zero
 291                 z := x/y;       ... chopped quotient, possibly inexact
 292                 If(not I) then {        ... if the quotient is exact
 293                     if(z=y) {
 294                         I := i;  ... restore inexact flag
 295                         R := r;  ... restore rounded mode
 296                         return sqrt(x):=y.
 297                     } else {
 298                         z := z - ulp;   ... special rounding
 299                     }
 300                 }
 301                 i := TRUE;              ... sqrt(x) is inexact
 302                 If (r=RN) then z=z+ulp  ... rounded-to-nearest
 303                 If (r=RP) then {        ... round-toward-+inf
 304                     y = y+ulp; z=z+ulp;
 305                 }
 306                 y := y+z;               ... chopped sum
 307                 y0:=y0-0x00100000;      ... y := y/2 is correctly rounded.
 308                 I := i;                 ... restore inexact flag
 309                 R := r;                 ... restore rounded mode
 310                 return sqrt(x):=y.
 311
 312     (4) Special cases
 313
 314         Square root of +inf, +-0, or NaN is itself;
 315         Square root of a negative number is NaN with invalid signal.
 316
 317
 318 B.  sqrt(x) by Reciproot Iteration
 319
 320    (1)  Initial approximation
 321
 322         Let x0 and x1 be the leading and the trailing 32-bit words of
 323         a floating point number x (in IEEE double format) respectively
 324         (see section A). By performing shifs and subtracts on x0 and y0,
 325         we obtain a 7.8-bit approximation of 1/sqrt(x) as follows.
 326
 327             k := 0x5fe80000 - (x0>>1);
 328             y0:= k - T2[63&(k>>14)].    ... y ~ 1/sqrt(x) to 7.8 bits
 329
 330         Here k is a 32-bit integer and T2[] is an integer array
 331         containing correction terms. Now magically the floating
 332         value of y (y's leading 32-bit word is y0, the value of
 333         its trailing word y1 is set to zero) approximates 1/sqrt(x)
 334         to almost 7.8-bit.
 335
 336         Value of T2:
 337         static int T2[64]= {
 338         0x1500, 0x2ef8, 0x4d67, 0x6b02, 0x87be, 0xa395, 0xbe7a, 0xd866,
 339         0xf14a, 0x1091b,0x11fcd,0x13552,0x14999,0x15c98,0x16e34,0x17e5f,
 340         0x18d03,0x19a01,0x1a545,0x1ae8a,0x1b5c4,0x1bb01,0x1bfde,0x1c28d,
 341         0x1c2de,0x1c0db,0x1ba73,0x1b11c,0x1a4b5,0x1953d,0x18266,0x16be0,
 342         0x1683e,0x179d8,0x18a4d,0x19992,0x1a789,0x1b445,0x1bf61,0x1c989,
 343         0x1d16d,0x1d77b,0x1dddf,0x1e2ad,0x1e5bf,0x1e6e8,0x1e654,0x1e3cd,
 344         0x1df2a,0x1d635,0x1cb16,0x1be2c,0x1ae4e,0x19bde,0x1868e,0x16e2e,
 345         0x1527f,0x1334a,0x11051,0xe951, 0xbe01, 0x8e0d, 0x5924, 0x1edd,};
 346
 347     (2) Iterative refinement
 348
 349         Apply Reciproot iteration three times to y and multiply the
 350         result by x to get an approximation z that matches sqrt(x)
 351         to about 1 ulp. To be exact, we will have
 352                 -1ulp < sqrt(x)-z<1.0625ulp.
 353
 354         ... set rounding mode to Round-to-nearest
 355            y := y*(1.5-0.5*x*y*y)       ... almost 15 sig. bits to 1/sqrt(x)
 356            y := y*((1.5-2^-30)+0.5*x*y*y)... about 29 sig. bits to 1/sqrt(x)
 357         ... special arrangement for better accuracy
 358            z := x*y                     ... 29 bits to sqrt(x), with z*y<1
 359            z := z + 0.5*z*(1-z*y)       ... about 1 ulp to sqrt(x)
 360
 361         Remark 2. The constant 1.5-2^-30 is chosen to bias the error so that
 362         (a) the term z*y in the final iteration is always less than 1;
 363         (b) the error in the final result is biased upward so that
 364                 -1 ulp < sqrt(x) - z < 1.0625 ulp
 365             instead of |sqrt(x)-z|<1.03125ulp.
 366
 367     (3) Final adjustment
 368
 369         By twiddling y's last bit it is possible to force y to be
 370         correctly rounded according to the prevailing rounding mode
 371         as follows. Let r and i be copies of the rounding mode and
 372         inexact flag before entering the square root program. Also we
 373         use the expression y+-ulp for the next representable floating
 374         numbers (up and down) of y. Note that y+-ulp = either fixed
 375         point y+-1, or multiply y by nextafter(1,+-inf) in chopped
 376         mode.
 377
 378         R := RZ;                ... set rounding mode to round-toward-zero
 379         switch(r) {
 380             case RN:            ... round-to-nearest
 381                if(x<= z*(z-ulp)...chopped) z = z - ulp; else
 382                if(x<= z*(z+ulp)...chopped) z = z; else z = z+ulp;
 383                break;
 384             case RZ:case RM:    ... round-to-zero or round-to--inf
 385                R:=RP;           ... reset rounding mod to round-to-+inf
 386                if(x<z*z ... rounded up) z = z - ulp; else
 387                if(x>=(z+ulp)*(z+ulp) ...rounded up) z = z+ulp;
 388                break;
 389             case RP:            ... round-to-+inf
 390                if(x>(z+ulp)*(z+ulp)...chopped) z = z+2*ulp; else
 391                if(x>z*z ...chopped) z = z+ulp;
 392                break;
 393         }
 394
 395         Remark 3. The above comparisons can be done in fixed point. For
 396         example, to compare x and w=z*z chopped, it suffices to compare
 397         x1 and w1 (the trailing parts of x and w), regarding them as
 398         two's complement integers.
 399
 400         ...Is z an exact square root?
 401         To determine whether z is an exact square root of x, let z1 be the
 402         trailing part of z, and also let x0 and x1 be the leading and
 403         trailing parts of x.
 404
 405         If ((z1&0x03ffffff)!=0) ... not exact if trailing 26 bits of z!=0
 406             I := 1;             ... Raise Inexact flag: z is not exact
 407         else {
 408             j := 1 - [(x0>>20)&1]       ... j = logb(x) mod 2
 409             k := z1 >> 26;              ... get z's 25-th and 26-th
 410                                             fraction bits
 411             I := i or (k&j) or ((k&(j+j+1))!=(x1&3));
 412         }
 413         R:= r           ... restore rounded mode
 414         return sqrt(x):=z.
 415
 416         If multiplication is cheaper then the foregoing red tape, the
 417         Inexact flag can be evaluated by
 418
 419             I := i;
 420             I := (z*z!=x) or I.
 421
 422         Note that z*z can overwrite I; this value must be sensed if it is
 423         True.
 424
 425         Remark 4. If z*z = x exactly, then bit 25 to bit 0 of z1 must be
 426         zero.
 427
 428                     --------------------
 429                 z1: |        f2        |
 430                     --------------------
 431                 bit 31             bit 0
 432
 433         Further more, bit 27 and 26 of z1, bit 0 and 1 of x1, and the odd
 434         or even of logb(x) have the following relations:
 435
 436         -------------------------------------------------
 437         bit 27,26 of z1         bit 1,0 of x1   logb(x)
 438         -------------------------------------------------
 439         00                      00              odd and even
 440         01                      01              even
 441         10                      10              odd
 442         10                      00              even
 443         11                      01              even
 444         -------------------------------------------------
 445
 446     (4) Special cases (see (4) of Section A).
 447
 448  */
 449