1 | /* Compute x^2 + y^2 - 1, without large cancellation error. |
2 | Copyright (C) 2012-2018 Free Software Foundation, Inc. |
3 | This file is part of the GNU C Library. |
4 | |
5 | The GNU C Library is free software; you can redistribute it and/or |
6 | modify it under the terms of the GNU Lesser General Public |
7 | License as published by the Free Software Foundation; either |
8 | version 2.1 of the License, or (at your option) any later version. |
9 | |
10 | The GNU C Library is distributed in the hope that it will be useful, |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | Lesser General Public License for more details. |
14 | |
15 | You should have received a copy of the GNU Lesser General Public |
16 | License along with the GNU C Library; if not, see |
17 | <http://www.gnu.org/licenses/>. */ |
18 | |
19 | #include <math.h> |
20 | #include <math_private.h> |
21 | #include <mul_split.h> |
22 | #include <stdlib.h> |
23 | |
24 | /* Calculate X + Y exactly and store the result in *HI + *LO. It is |
25 | given that |X| >= |Y| and the values are small enough that no |
26 | overflow occurs. */ |
27 | |
28 | static inline void |
29 | add_split (double *hi, double *lo, double x, double y) |
30 | { |
31 | /* Apply Dekker's algorithm. */ |
32 | *hi = x + y; |
33 | *lo = (x - *hi) + y; |
34 | } |
35 | |
36 | /* Compare absolute values of floating-point values pointed to by P |
37 | and Q for qsort. */ |
38 | |
39 | static int |
40 | compare (const void *p, const void *q) |
41 | { |
42 | double pd = fabs (*(const double *) p); |
43 | double qd = fabs (*(const double *) q); |
44 | if (pd < qd) |
45 | return -1; |
46 | else if (pd == qd) |
47 | return 0; |
48 | else |
49 | return 1; |
50 | } |
51 | |
52 | /* Return X^2 + Y^2 - 1, computed without large cancellation error. |
53 | It is given that 1 > X >= Y >= epsilon / 2, and that X^2 + Y^2 >= |
54 | 0.5. */ |
55 | |
56 | double |
57 | __x2y2m1 (double x, double y) |
58 | { |
59 | double vals[5]; |
60 | SET_RESTORE_ROUND (FE_TONEAREST); |
61 | mul_split (&vals[1], &vals[0], x, x); |
62 | mul_split (&vals[3], &vals[2], y, y); |
63 | vals[4] = -1.0; |
64 | qsort (vals, 5, sizeof (double), compare); |
65 | /* Add up the values so that each element of VALS has absolute value |
66 | at most equal to the last set bit of the next nonzero |
67 | element. */ |
68 | for (size_t i = 0; i <= 3; i++) |
69 | { |
70 | add_split (&vals[i + 1], &vals[i], vals[i + 1], vals[i]); |
71 | qsort (vals + i + 1, 4 - i, sizeof (double), compare); |
72 | } |
73 | /* Now any error from this addition will be small. */ |
74 | return vals[4] + vals[3] + vals[2] + vals[1] + vals[0]; |
75 | } |
76 | |