| 1 |
#include <stdint.h> |
| 2 |
#include <math.h> |
| 3 |
#include "libm.h" |
| 4 |
#include "sqrt_data.h" |
| 5 |
|
| 6 |
#define FENV_SUPPORT 1 |
| 7 |
|
| 8 |
/* returns a*b*2^-32 - e, with error 0 <= e < 1. */ |
| 9 |
static inline uint32_t mul32(uint32_t a, uint32_t b) |
| 10 |
{ |
| 11 |
return (uint64_t)a*b >> 32; |
| 12 |
} |
| 13 |
|
| 14 |
/* returns a*b*2^-64 - e, with error 0 <= e < 3. */ |
| 15 |
static inline uint64_t mul64(uint64_t a, uint64_t b) |
| 16 |
{ |
| 17 |
uint64_t ahi = a>>32; |
| 18 |
uint64_t alo = a&0xffffffff; |
| 19 |
uint64_t bhi = b>>32; |
| 20 |
uint64_t blo = b&0xffffffff; |
| 21 |
return ahi*bhi + (ahi*blo >> 32) + (alo*bhi >> 32); |
| 22 |
} |
| 23 |
|
| 24 |
double sqrt(double x) |
| 25 |
{ |
| 26 |
uint64_t ix, top, m; |
| 27 |
|
| 28 |
/* special case handling. */ |
| 29 |
ix = asuint64(x); |
| 30 |
top = ix >> 52; |
| 31 |
if (predict_false(top - 0x001 >= 0x7ff - 0x001)) { |
| 32 |
/* x < 0x1p-1022 or inf or nan. */ |
| 33 |
if (ix * 2 == 0) |
| 34 |
return x; |
| 35 |
if (ix == 0x7ff0000000000000) |
| 36 |
return x; |
| 37 |
if (ix > 0x7ff0000000000000) |
| 38 |
return __math_invalid(x); |
| 39 |
/* x is subnormal, normalize it. */ |
| 40 |
ix = asuint64(x * 0x1p52); |
| 41 |
top = ix >> 52; |
| 42 |
top -= 52; |
| 43 |
} |
| 44 |
|
| 45 |
/* argument reduction: |
| 46 |
x = 4^e m; with integer e, and m in [1, 4) |
| 47 |
m: fixed point representation [2.62] |
| 48 |
2^e is the exponent part of the result. */ |
| 49 |
int even = top & 1; |
| 50 |
m = (ix << 11) | 0x8000000000000000; |
| 51 |
if (even) m >>= 1; |
| 52 |
top = (top + 0x3ff) >> 1; |
| 53 |
|
| 54 |
/* approximate r ~ 1/sqrt(m) and s ~ sqrt(m) when m in [1,4) |
| 55 |
|
| 56 |
initial estimate: |
| 57 |
7bit table lookup (1bit exponent and 6bit significand). |
| 58 |
|
| 59 |
iterative approximation: |
| 60 |
using 2 goldschmidt iterations with 32bit int arithmetics |
| 61 |
and a final iteration with 64bit int arithmetics. |
| 62 |
|
| 63 |
details: |
| 64 |
|
| 65 |
the relative error (e = r0 sqrt(m)-1) of a linear estimate |
| 66 |
(r0 = a m + b) is |e| < 0.085955 ~ 0x1.6p-4 at best, |
| 67 |
a table lookup is faster and needs one less iteration |
| 68 |
6 bit lookup table (128b) gives |e| < 0x1.f9p-8 |
| 69 |
7 bit lookup table (256b) gives |e| < 0x1.fdp-9 |
| 70 |
for single and double prec 6bit is enough but for quad |
| 71 |
prec 7bit is needed (or modified iterations). to avoid |
| 72 |
one more iteration >=13bit table would be needed (16k). |
| 73 |
|
| 74 |
a newton-raphson iteration for r is |
| 75 |
w = r*r |
| 76 |
u = 3 - m*w |
| 77 |
r = r*u/2 |
| 78 |
can use a goldschmidt iteration for s at the end or |
| 79 |
s = m*r |
| 80 |
|
| 81 |
first goldschmidt iteration is |
| 82 |
s = m*r |
| 83 |
u = 3 - s*r |
| 84 |
r = r*u/2 |
| 85 |
s = s*u/2 |
| 86 |
next goldschmidt iteration is |
| 87 |
u = 3 - s*r |
| 88 |
r = r*u/2 |
| 89 |
s = s*u/2 |
| 90 |
and at the end r is not computed only s. |
| 91 |
|
| 92 |
they use the same amount of operations and converge at the |
| 93 |
same quadratic rate, i.e. if |
| 94 |
r1 sqrt(m) - 1 = e, then |
| 95 |
r2 sqrt(m) - 1 = -3/2 e^2 - 1/2 e^3 |
| 96 |
the advantage of goldschmidt is that the mul for s and r |
| 97 |
are independent (computed in parallel), however it is not |
| 98 |
"self synchronizing": it only uses the input m in the |
| 99 |
first iteration so rounding errors accumulate. at the end |
| 100 |
or when switching to larger precision arithmetics rounding |
| 101 |
errors dominate so the first iteration should be used. |
| 102 |
|
| 103 |
the fixed point representations are |
| 104 |
m: 2.30 r: 0.32, s: 2.30, d: 2.30, u: 2.30, three: 2.30 |
| 105 |
and after switching to 64 bit |
| 106 |
m: 2.62 r: 0.64, s: 2.62, d: 2.62, u: 2.62, three: 2.62 */ |
| 107 |
|
| 108 |
static const uint64_t three = 0xc0000000; |
| 109 |
uint64_t r, s, d, u, i; |
| 110 |
|
| 111 |
i = (ix >> 46) % 128; |
| 112 |
r = (uint32_t)__rsqrt_tab[i] << 16; |
| 113 |
/* |r sqrt(m) - 1| < 0x1.fdp-9 */ |
| 114 |
s = mul32(m>>32, r); |
| 115 |
/* |s/sqrt(m) - 1| < 0x1.fdp-9 */ |
| 116 |
d = mul32(s, r); |
| 117 |
u = three - d; |
| 118 |
r = mul32(r, u) << 1; |
| 119 |
/* |r sqrt(m) - 1| < 0x1.7bp-16 */ |
| 120 |
s = mul32(s, u) << 1; |
| 121 |
/* |s/sqrt(m) - 1| < 0x1.7bp-16 */ |
| 122 |
d = mul32(s, r); |
| 123 |
u = three - d; |
| 124 |
r = mul32(r, u) << 1; |
| 125 |
/* |r sqrt(m) - 1| < 0x1.3704p-29 (measured worst-case) */ |
| 126 |
r = r << 32; |
| 127 |
s = mul64(m, r); |
| 128 |
d = mul64(s, r); |
| 129 |
u = (three<<32) - d; |
| 130 |
s = mul64(s, u); /* repr: 3.61 */ |
| 131 |
/* -0x1p-57 < s - sqrt(m) < 0x1.8001p-61 */ |
| 132 |
s = (s - 2) >> 9; /* repr: 12.52 */ |
| 133 |
/* -0x1.09p-52 < s - sqrt(m) < -0x1.fffcp-63 */ |
| 134 |
|
| 135 |
/* s < sqrt(m) < s + 0x1.09p-52, |
| 136 |
compute nearest rounded result: |
| 137 |
the nearest result to 52 bits is either s or s+0x1p-52, |
| 138 |
we can decide by comparing (2^52 s + 0.5)^2 to 2^104 m. */ |
| 139 |
uint64_t d0, d1, d2; |
| 140 |
double y, t; |
| 141 |
d0 = (m << 42) - s*s; |
| 142 |
d1 = s - d0; |
| 143 |
d2 = d1 + s + 1; |
| 144 |
s += d1 >> 63; |
| 145 |
s &= 0x000fffffffffffff; |
| 146 |
s |= top << 52; |
| 147 |
y = asdouble(s); |
| 148 |
if (FENV_SUPPORT) { |
| 149 |
/* handle rounding modes and inexact exception: |
| 150 |
only (s+1)^2 == 2^42 m case is exact otherwise |
| 151 |
add a tiny value to cause the fenv effects. */ |
| 152 |
uint64_t tiny = predict_false(d2==0) ? 0 : 0x0010000000000000; |
| 153 |
tiny |= (d1^d2) & 0x8000000000000000; |
| 154 |
t = asdouble(tiny); |
| 155 |
y = eval_as_double(y + t); |
| 156 |
} |
| 157 |
return y; |
| 158 |
} |