1/* Compute full X * Y for double type.
2 Copyright (C) 2013-2021 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 <https://www.gnu.org/licenses/>. */
18
19#ifndef _MUL_SPLIT_H
20#define _MUL_SPLIT_H
21
22#include <float.h>
23
24/* Calculate X * Y exactly and store the result in *HI + *LO. It is
25 given that the values are small enough that no overflow occurs and
26 large enough (or zero) that no underflow occurs. */
27
28static void
29mul_split (double *hi, double *lo, double x, double y)
30{
31#ifdef __FP_FAST_FMA
32 /* Fast built-in fused multiply-add. */
33 *hi = x * y;
34 *lo = __builtin_fma (x, y, -*hi);
35#else
36 /* Apply Dekker's algorithm. */
37 *hi = x * y;
38# define C ((1 << (DBL_MANT_DIG + 1) / 2) + 1)
39 double x1 = x * C;
40 double y1 = y * C;
41# undef C
42 x1 = (x - x1) + x1;
43 y1 = (y - y1) + y1;
44 double x2 = x - x1;
45 double y2 = y - y1;
46 *lo = (((x1 * y1 - *hi) + x1 * y2) + x2 * y1) + x2 * y2;
47#endif
48}
49
50/* Add a + b exactly, such that *hi + *lo = a + b.
51 Assumes |a| >= |b| and rounding to nearest. */
52static inline void
53fast_two_sum (double *hi, double *lo, double a, double b)
54{
55 double e;
56
57 *hi = a + b;
58 e = *hi - a; /* exact */
59 *lo = b - e; /* exact */
60 /* Now *hi + *lo = a + b exactly. */
61}
62
63/* Multiplication of two floating-point expansions: *hi + *lo is an
64 approximation of (h1+l1)*(h2+l2), assuming |l1| <= 1/2*ulp(h1)
65 and |l2| <= 1/2*ulp(h2) and rounding to nearest. */
66static inline void
67mul_expansion (double *hi, double *lo, double h1, double l1,
68 double h2, double l2)
69{
70 double r, e;
71
72 mul_split (hi, lo, h1, h2);
73 r = h1 * l2 + h2 * l1;
74 /* Now add r to (hi,lo) using fast two-sum, where we know |r| < |hi|. */
75 fast_two_sum (hi, &e, *hi, r);
76 *lo -= e;
77}
78
79/* Calculate X / Y and store the approximate result in *HI + *LO. It is
80 assumed that Y is not zero, that no overflow nor underflow occurs, and
81 rounding is to nearest. */
82static inline void
83div_split (double *hi, double *lo, double x, double y)
84{
85 double a, b;
86
87 *hi = x / y;
88 mul_split (&a, &b, *hi, y);
89 /* a + b = hi*y, which should be near x. */
90 a = x - a; /* huge cancellation */
91 a = a - b;
92 /* Now x ~ hi*y + a thus x/y ~ hi + a/y. */
93 *lo = a / y;
94}
95
96/* Division of two floating-point expansions: *hi + *lo is an
97 approximation of (h1+l1)/(h2+l2), assuming |l1| <= 1/2*ulp(h1)
98 and |l2| <= 1/2*ulp(h2), h2+l2 is not zero, and rounding to nearest. */
99static inline void
100div_expansion (double *hi, double *lo, double h1, double l1,
101 double h2, double l2)
102{
103 double r, e;
104
105 div_split (hi, lo, h1, h2);
106 /* (h1+l1)/(h2+l2) ~ h1/h2 + (l1*h2 - l2*h1)/h2^2 */
107 r = (l1 * h2 - l2 * h1) / (h2 * h2);
108 /* Now add r to (hi,lo) using fast two-sum, where we know |r| < |hi|. */
109 fast_two_sum (hi, &e, *hi, r);
110 *lo += e;
111 /* Renormalize since |lo| might be larger than 0.5 ulp(hi). */
112 fast_two_sum (hi, lo, *hi, *lo);
113}
114
115#endif /* _MUL_SPLIT_H */
116