1//===-- Utilities for double-double data type. ------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LLVM_LIBC_SRC___SUPPORT_FPUTIL_DOUBLE_DOUBLE_H
10#define LLVM_LIBC_SRC___SUPPORT_FPUTIL_DOUBLE_DOUBLE_H
11
12#include "multiply_add.h"
13#include "src/__support/common.h"
14#include "src/__support/macros/config.h"
15#include "src/__support/macros/optimization.h" // LIBC_DO_NOT_OPTIMIZE
16#include "src/__support/macros/properties/cpu_features.h" // LIBC_TARGET_CPU_HAS_FMA
17#include "src/__support/number_pair.h"
18
19namespace LIBC_NAMESPACE_DECL {
20namespace fputil {
21
22template <typename T> struct DefaultSplit;
23template <> struct DefaultSplit<float> {
24 static constexpr size_t VALUE = 12;
25};
26template <> struct DefaultSplit<double> {
27 static constexpr size_t VALUE = 27;
28};
29
30using DoubleDouble = NumberPair<double>;
31using FloatFloat = NumberPair<float>;
32
33// Dekker's FastTwoSum:
34// r_hi + r_lo ~ a + b
35// In precision `p`, it's exact if `lsb(a) >= ulp(b)` and one of the following
36// conditions satisfies:
37// (i) rounding mode = RN
38// (ii) e_a - e_b <= p
39// (iii) rounding mode = RD and b >= 0
40// (iv) rounding mode = RU and b <= 0
41// (v) rounding mode = RZ and ab >= 0
42// Otherwise, the errors err = (a + b) - (r_hi + r_lo) is bounded by:
43// |err| <= 2^(-2p + 1) * ufp(a + b) <= 2^(-2p + 1) * ufp(r_hi)
44// when `lsb(a) >= ulp(b)`.
45// In particular,
46// |err| <= 2^-47 * ufp(r_hi) for single precision,
47// <= 2^-105 * ufp(r_hi) for double precision.
48// If the condition `lsb(a) >= ulp(b)` does NOT satisfy, then:
49// |err| < 3 * 2^(-p) * |r_hi|.
50// Reference:
51// Jeannerod, C.-P. and Zimmermann, P., "FastTwoSum revisited", ARITH 2025,
52// <https://www.arith2025.org/proceedings/215900a141.pdf>.
53template <bool FAST2SUM = true, typename T = double>
54LIBC_INLINE constexpr NumberPair<T> exact_add(T a, T b) {
55 NumberPair<T> r;
56 if constexpr (FAST2SUM) {
57 r.hi = a + b;
58 T t = r.hi - a;
59 r.lo = b - t;
60 } else {
61 r.hi = a + b;
62 T t1 = r.hi - a;
63 T t2 = r.hi - t1;
64 T t3 = b - t1;
65 T t4 = a - t2;
66 r.lo = t3 + t4;
67 }
68 return r;
69}
70
71template <bool FAST2SUM = true, typename T = double>
72LIBC_INLINE constexpr NumberPair<T> exact_sub(T a, T b) {
73 NumberPair<T> r;
74 if constexpr (FAST2SUM) {
75 r.hi = a - b;
76 T t = a - r.hi;
77 r.lo = t - b;
78 } else {
79 r.hi = a - b;
80 T t1 = r.hi - a;
81 T t2 = r.hi - t1;
82 T t3 = a - t2;
83 T t4 = b + t1;
84 r.lo = t3 - t4;
85 }
86 return r;
87}
88
89// Following the above analysis of FastTwoSum,
90// If `lsb(a.hi) >= ulp(b.hi)`, then the errors:
91// err = (a.hi + a.lo + b.hi + b.lo) - (r.hi - r.lo) is bounded by:
92// |err| < 2^(-2p) * ufp(r.hi) + 2^(-p + 2) * ufp(a.lo + b.lo).
93template <bool FAST2SUM = true, typename T>
94LIBC_INLINE constexpr NumberPair<T> add(const NumberPair<T> &a,
95 const NumberPair<T> &b) {
96 NumberPair<T> r = exact_add<FAST2SUM>(a.hi, b.hi);
97 T lo = a.lo + b.lo;
98 T r_lo = r.lo + lo;
99 return exact_add<FAST2SUM>(r.hi, r_lo);
100}
101
102// Assumption: when FAST2SUM = true, |a.hi| >= |b|
103template <bool FAST2SUM = true, typename T>
104LIBC_INLINE constexpr NumberPair<T> add(const NumberPair<T> &a, T b) {
105 NumberPair<T> r = exact_add<FAST2SUM>(a.hi, b);
106 T r_lo = r.lo + a.lo;
107 return exact_add<FAST2SUM>(r.hi, r_lo);
108}
109
110// Assumption: when FAST2SUM = true, |a| >= |b.hi|.
111template <bool FAST2SUM = true, typename T>
112LIBC_INLINE constexpr NumberPair<T> add(T a, const NumberPair<T> &b) {
113 NumberPair<T> r = exact_add<FAST2SUM>(a, b.hi);
114 T r_lo = r.lo + b.lo;
115 return exact_add<FAST2SUM>(r.hi, r_lo);
116}
117
118// Assumption: when FAST2SUM = true, |a.hi| >= |b.hi|.
119template <bool FAST2SUM = true, typename T>
120LIBC_INLINE constexpr NumberPair<T> sub(const NumberPair<T> &a,
121 const NumberPair<T> &b) {
122 NumberPair<T> r = exact_sub<FAST2SUM>(a.hi, b.hi);
123 T lo = a.lo - b.lo;
124 T r_lo = r.lo + lo;
125 return exact_add<FAST2SUM>(r.hi, r_lo);
126}
127
128// Assumption: when FAST2SUM = true, |a.hi| >= |b|.
129template <bool FAST2SUM = true, typename T>
130LIBC_INLINE constexpr NumberPair<T> sub(const NumberPair<T> &a, T b) {
131 NumberPair<T> r = exact_sub<FAST2SUM>(a.hi, b);
132 T r_lo = r.lo + a.lo;
133 return exact_add<FAST2SUM>(r.hi, r_lo);
134}
135
136// Assumption: when FAST2SUM = true, |a| >= |b.hi|.
137template <bool FAST2SUM = true, typename T>
138LIBC_INLINE constexpr NumberPair<T> sub(T a, const NumberPair<T> &b) {
139 NumberPair<T> r = exact_sub<FAST2SUM>(a, b.hi);
140 T r_lo = r.lo - b.lo;
141 return exact_add<FAST2SUM>(r.hi, r_lo);
142}
143
144// Veltkamp's Splitting for double precision.
145// Note: This is proved to be correct for all rounding modes:
146// Zimmermann, P., "Note on the Veltkamp/Dekker Algorithms with Directed
147// Roundings," https://inria.hal.science/hal-04480440.
148// Default splitting constant = 2^ceil(prec(double)/2) + 1 = 2^27 + 1.
149template <typename T = double, size_t N = DefaultSplit<T>::VALUE>
150LIBC_INLINE constexpr NumberPair<T> split(T a) {
151 NumberPair<T> r;
152 // CN = 2^N.
153 constexpr T CN = static_cast<T>(1 << N);
154 constexpr T C = CN + T(1);
155 T t1 = C * a;
156 T t2 = a - t1;
157 r.hi = t1 + t2;
158 r.lo = a - r.hi;
159 return r;
160}
161
162// Helper for non-fma exact mult where the first number is already split.
163template <typename T = double, size_t SPLIT_B = DefaultSplit<T>::VALUE>
164LIBC_INLINE constexpr NumberPair<T> exact_mult(const NumberPair<T> &as, T a,
165 T b) {
166 NumberPair<T> bs = split<T, SPLIT_B>(b);
167 NumberPair<T> r;
168
169 r.hi = a * b;
170 T t1 = as.hi * bs.hi - r.hi;
171 T t2 = as.hi * bs.lo + t1;
172 T t3 = as.lo * bs.hi + t2;
173 r.lo = as.lo * bs.lo + t3;
174
175 return r;
176}
177
178// The templated exact multiplication needs template version of
179// LIBC_TARGET_CPU_HAS_FMA_* macro to correctly select the implementation.
180// These can be moved to "src/__support/macros/properties/cpu_features.h" if
181// other part of libc needed.
182template <typename T> struct TargetHasFmaInstruction {
183 static constexpr bool VALUE = false;
184};
185
186#ifdef LIBC_TARGET_CPU_HAS_FMA_FLOAT
187template <> struct TargetHasFmaInstruction<float> {
188 static constexpr bool VALUE = true;
189};
190#endif // LIBC_TARGET_CPU_HAS_FMA_FLOAT
191
192#ifdef LIBC_TARGET_CPU_HAS_FMA_DOUBLE
193template <> struct TargetHasFmaInstruction<double> {
194 static constexpr bool VALUE = true;
195};
196#endif // LIBC_TARGET_CPU_HAS_FMA_DOUBLE
197
198// Note: When FMA instruction is not available, the `exact_mult` function is
199// only correct for round-to-nearest mode. See:
200// Zimmermann, P., "Note on the Veltkamp/Dekker Algorithms with Directed
201// Roundings," https://inria.hal.science/hal-04480440.
202// Using Theorem 1 in the paper above, without FMA instruction, if we restrict
203// the generated constants to precision <= 51, and splitting it by 2^28 + 1,
204// then a * b = r.hi + r.lo is exact for all rounding modes.
205template <typename T = double, size_t SPLIT_B = DefaultSplit<T>::VALUE>
206LIBC_INLINE LIBC_CONSTEXPR NumberPair<T> exact_mult(T a, T b) {
207 NumberPair<T> r;
208
209 if constexpr (TargetHasFmaInstruction<T>::VALUE) {
210 r.hi = a * b;
211 // Prevent `-r.hi` inside `multiply_sub` from being rewritten into
212 // `a * (-b)` when `a * b` is duplicated (e.g. by SLP vectorization), which
213 // breaks directed rounding modes (`RU(a * (-b)) != -RU(a * b)`).
214 LIBC_DO_NOT_OPTIMIZE_ROUNDING(r.hi);
215 r.lo = fputil::multiply_sub(a, b, r.hi);
216 } else {
217 // Dekker's Product.
218 NumberPair<T> as = split(a);
219
220 r = exact_mult<T, SPLIT_B>(as, a, b);
221 }
222
223 return r;
224}
225
226template <typename T = double>
227LIBC_INLINE NumberPair<T> quick_mult(T a, const NumberPair<T> &b) {
228 NumberPair<T> r = exact_mult(a, b.hi);
229 r.lo = multiply_add(a, b.lo, r.lo);
230 return r;
231}
232
233template <size_t SPLIT_B = 27>
234LIBC_INLINE constexpr DoubleDouble quick_mult(const DoubleDouble &a,
235 const DoubleDouble &b) {
236 DoubleDouble r = exact_mult<double, SPLIT_B>(a.hi, b.hi);
237 double t1 = multiply_add(x: a.hi, y: b.lo, z: r.lo);
238 double t2 = multiply_add(x: a.lo, y: b.hi, z: t1);
239 r.lo = t2;
240 return r;
241}
242
243// Assuming |c| >= |a * b|.
244template <>
245LIBC_INLINE DoubleDouble multiply_add<DoubleDouble>(const DoubleDouble &a,
246 const DoubleDouble &b,
247 const DoubleDouble &c) {
248 return add(a: c, b: quick_mult(a, b));
249}
250
251// Assuming |a * b| >= |c|.
252template <>
253LIBC_INLINE DoubleDouble multiply_sub<DoubleDouble>(const DoubleDouble &a,
254 const DoubleDouble &b,
255 const DoubleDouble &c) {
256 return sub(a: quick_mult(a, b), b: c);
257}
258
259// Assuming |a| >= |b * c|.
260template <>
261LIBC_INLINE DoubleDouble sub_multiply<DoubleDouble>(const DoubleDouble &a,
262 const DoubleDouble &b,
263 const DoubleDouble &c) {
264 return sub(a, b: quick_mult(a: b, b: c));
265}
266
267// Accurate double-double division, following Karp-Markstein's trick for
268// division, implemented in the CORE-MATH project at:
269// https://gitlab.inria.fr/core-math/core-math/-/blob/master/src/binary64/tan/tan.c#L1855
270//
271// Error bounds:
272// Let a = ah + al, b = bh + bl.
273// Let r = rh + rl be the approximation of (ah + al) / (bh + bl).
274// Then:
275// (ah + al) / (bh + bl) - rh =
276// = ((ah - bh * rh) + (al - bl * rh)) / (bh + bl)
277// = (1 + O(bl/bh)) * ((ah - bh * rh) + (al - bl * rh)) / bh
278// Let q = round(1/bh), then the above expressions are approximately:
279// = (1 + O(bl / bh)) * (1 + O(2^-52)) * q * ((ah - bh * rh) + (al - bl * rh))
280// So we can compute:
281// rl = q * (ah - bh * rh) + q * (al - bl * rh)
282// as accurate as possible, then the error is bounded by:
283// |(ah + al) / (bh + bl) - (rh + rl)| < O(bl/bh) * (2^-52 + al/ah + bl/bh)
284template <typename T>
285LIBC_INLINE NumberPair<T> div(const NumberPair<T> &a, const NumberPair<T> &b) {
286 NumberPair<T> r;
287 T q = T(1) / b.hi;
288 r.hi = a.hi * q;
289 LIBC_DO_NOT_OPTIMIZE_ROUNDING(r.hi);
290
291#ifdef LIBC_TARGET_CPU_HAS_FMA
292 T e_hi = fputil::sub_multiply(a.hi, b.hi, r.hi);
293 T e_lo = fputil::sub_multiply(a.lo, b.lo, r.hi);
294#else
295 NumberPair<T> b_hi_r_hi = fputil::exact_mult(b.hi, -r.hi);
296 NumberPair<T> b_lo_r_hi = fputil::exact_mult(b.lo, -r.hi);
297 T e_hi = (a.hi + b_hi_r_hi.hi) + b_hi_r_hi.lo;
298 T e_lo = (a.lo + b_lo_r_hi.hi) + b_lo_r_hi.lo;
299#endif // LIBC_TARGET_CPU_HAS_FMA
300
301 r.lo = q * (e_hi + e_lo);
302 return r;
303}
304
305} // namespace fputil
306} // namespace LIBC_NAMESPACE_DECL
307
308#endif // LLVM_LIBC_SRC___SUPPORT_FPUTIL_DOUBLE_DOUBLE_H
309