source: mainline/uspace/lib/math/generic/sqrt.c@ 048a6e9

Last change on this file since 048a6e9 was 048a6e9, checked in by Maurizio Lombardi <mlombard@…>, 4 years ago

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