Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
GenericPacketMathDoubleWord.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2018-2025 Rasmus Munk Larsen <rmlarsen@gmail.com>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9// SPDX-License-Identifier: MPL-2.0
10
11#ifndef EIGEN_ARCH_GENERIC_PACKET_MATH_DOUBLE_WORD_H
12#define EIGEN_ARCH_GENERIC_PACKET_MATH_DOUBLE_WORD_H
13
14// IWYU pragma: private
15#include "../../InternalHeaderCheck.h"
16
17namespace Eigen {
18namespace internal {
19
20// This function splits x into the nearest integer n and fractional part r,
21// such that x = n + r holds exactly.
22template <typename Packet>
23EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void absolute_split(const Packet& x, Packet& n, Packet& r) {
24 n = pround(x);
25 r = psub(x, n);
26}
27
28// Knuth two-sum: x + y = s_hi + s_lo exactly, with no magnitude ordering required.
29template <typename Packet>
30EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void twosum(const Packet& x, const Packet& y, Packet& s_hi, Packet& s_lo) {
31 s_hi = padd(x, y);
32 pbarrier(s_hi);
33 Packet y_part = psub(s_hi, x);
34 pbarrier(y_part);
35 Packet x_part = psub(s_hi, y_part);
36 pbarrier(x_part);
37 Packet x_err = psub(x, x_part);
38 pbarrier(x_err);
39 Packet y_err = psub(y, y_part);
40 pbarrier(y_err);
41 s_lo = padd(x_err, y_err);
42}
43
44// This function computes the sum {s_hi, s_lo}, such that x + y = s_hi + s_lo
45// holds exactly, and s_hi = fl(x+y), if |x| >= |y|.
46template <typename Packet>
47EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void fast_twosum(const Packet& x, const Packet& y, Packet& s_hi, Packet& s_lo) {
48 s_hi = padd(x, y);
49 const Packet t = psub(s_hi, x);
50 s_lo = psub(y, t);
51}
52
53#ifdef EIGEN_VECTORIZE_FMA
54// Given x, y, and xy = fl(x*y), return the residual such that x*y = xy + residual exactly.
55template <typename Packet, std::enable_if_t<!is_scalar<Packet>::value, int> = 0>
56EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet twoprod_low(const Packet& x, const Packet& y, const Packet& xy) {
57 return pmsub(x, y, xy);
58}
59
60template <typename Scalar, std::enable_if_t<is_scalar<Scalar>::value, int> = 0>
61EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Scalar twoprod_low(const Scalar& x, const Scalar& y, const Scalar& xy) {
62 // Error-free products require FMA even when EIGEN_SCALAR_MADD_USE_FMA disables fusion in scalar madd.
63 return twoprod_low_fma(x, y, xy);
64}
65
66// This function implements the extended precision product of
67// a pair of floating point numbers. Given {x, y}, it computes the pair
68// {p_hi, p_lo} such that x * y = p_hi + p_lo holds exactly and
69// p_hi = fl(x * y). PreventReassociation preserves the separately rounded non-FMA operations.
70template <typename Packet, bool PreventReassociation = false>
71EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void twoprod(const Packet& x, const Packet& y, Packet& p_hi, Packet& p_lo) {
72 p_hi = pmul(x, y);
73 p_lo = twoprod_low(x, y, p_hi);
74}
75
76#else
77
78// Dekker's product requires separately rounded operations. GCC's C++ default -ffp-contract=fast may fuse
79// fl(x*y) into its consumers, so use fma for scalar types where it is an instruction (has_fast_fma).
80// This does not prevent contraction in the remaining scalar or packet fallback paths.
81template <typename Scalar, std::enable_if_t<has_fast_fma<Scalar>::value, int> = 0>
82EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Scalar twoprod_low(const Scalar& x, const Scalar& y, const Scalar& xy) {
83 return twoprod_low_fma(x, y, xy);
84}
85
86template <typename Scalar, bool PreventReassociation = false, std::enable_if_t<has_fast_fma<Scalar>::value, int> = 0>
87EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void twoprod(const Scalar& x, const Scalar& y, Scalar& p_hi, Scalar& p_lo) {
88 p_hi = x * y;
89 p_lo = twoprod_low(x, y, p_hi);
90}
91
92// This function implements the Veltkamp splitting. Given a floating point
93// number x it returns the pair {x_hi, x_lo} such that x_hi + x_lo = x holds
94// exactly and that half of the significand of x fits in x_hi.
95// This is Algorithm 3 from Jean-Michel Muller, "Elementary Functions",
96// 3rd edition, Birkh\"auser, 2016.
97template <typename Packet, bool PreventReassociation = false>
98EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void veltkamp_splitting(const Packet& x, Packet& x_hi, Packet& x_lo) {
99 using Scalar = typename unpacket_traits<Packet>::type;
100 constexpr int shift = (NumTraits<Scalar>::digits() + 1) / 2;
101 const Scalar shift_scale = Scalar(uint64_t(1) << shift); // Scalar constructor not necessarily constexpr.
102 Packet gamma = pmul(pset1<Packet>(shift_scale + Scalar(1)), x);
103 EIGEN_IF_CONSTEXPR (PreventReassociation) pbarrier(gamma);
104 Packet rho = psub(x, gamma);
105 EIGEN_IF_CONSTEXPR (PreventReassociation) pbarrier(rho);
106 x_hi = padd(rho, gamma);
107 EIGEN_IF_CONSTEXPR (PreventReassociation) pbarrier(x_hi);
108 x_lo = psub(x, x_hi);
109}
110
111// A version of twoprod that takes x, y, and fl(x*y) as input and returns the p_lo such that
112// x * y = xy + p_lo holds exactly. PreventReassociation preserves the separately rounded operations.
113template <typename Packet, bool PreventReassociation = false, std::enable_if_t<!has_fast_fma<Packet>::value, int> = 0>
114EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE Packet twoprod_low(const Packet& x, const Packet& y, const Packet& xy) {
115 Packet x_hi, x_lo, y_hi, y_lo;
116 veltkamp_splitting<Packet, PreventReassociation>(x, x_hi, x_lo);
117 veltkamp_splitting<Packet, PreventReassociation>(y, y_hi, y_lo);
118
119 Packet p_lo = pmsub(x_hi, y_hi, xy);
120 EIGEN_IF_CONSTEXPR (PreventReassociation) pbarrier(p_lo);
121 p_lo = pmadd(x_hi, y_lo, p_lo);
122 EIGEN_IF_CONSTEXPR (PreventReassociation) pbarrier(p_lo);
123 p_lo = pmadd(x_lo, y_hi, p_lo);
124 EIGEN_IF_CONSTEXPR (PreventReassociation) pbarrier(p_lo);
125 p_lo = pmadd(x_lo, y_lo, p_lo);
126 return p_lo;
127}
128
129// This function implements Dekker's algorithm for products x * y.
130// Given floating point numbers {x, y}, it computes {p_hi, p_lo} such that
131// x * y = p_hi + p_lo exactly and p_hi = fl(x * y).
132template <typename Packet, bool PreventReassociation = false, std::enable_if_t<!has_fast_fma<Packet>::value, int> = 0>
133EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void twoprod(const Packet& x, const Packet& y, Packet& p_hi, Packet& p_lo) {
134 Packet hi = pmul(x, y);
135 EIGEN_IF_CONSTEXPR (PreventReassociation) pbarrier(hi);
136 const Packet lo = twoprod_low<Packet, PreventReassociation>(x, y, hi);
137 p_hi = hi;
138 p_lo = lo;
139}
140
141#endif // EIGEN_VECTORIZE_FMA
142
143// Whether twoprod_full_range takes Dekker's product for Scalar rather than a software FMA: a binary IEEE format with
144// highest eps^6 >= min, so that an operand rescaled by eps^2 or 1 / eps^2 lands where the product is exact. libstdc++
145// reports is_iec559 for IBM double-double too, whose operations are not correctly rounded; emin = 1 - emax excludes it.
146// Other scalars keep the FMA, and so do GPU and SYCL devices, which fuse natively and have no optimization barrier.
147#if defined(EIGEN_VECTORIZE_FMA) || defined(EIGEN_GPUCC) || defined(EIGEN_USE_SYCL)
148template <typename Scalar>
149struct twoprod_full_range_uses_dekker : std::false_type {};
150#else
151template <typename Scalar>
152struct twoprod_full_range_uses_dekker
153 : bool_constant<!has_fast_fma<Scalar>::value && std::numeric_limits<Scalar>::is_iec559 &&
154 std::numeric_limits<Scalar>::radix == 2 &&
155 std::numeric_limits<Scalar>::min_exponent == 3 - std::numeric_limits<Scalar>::max_exponent &&
156 std::numeric_limits<Scalar>::max_exponent - std::numeric_limits<Scalar>::min_exponent >=
157 6 * std::numeric_limits<Scalar>::digits> {};
158
159// Veltkamp's splitting of x overflows for |x| > highest / 2^ceil(digits / 2), and Dekker's partial products lose bits
160// to underflow once ulp(x) ulp(y) < denorm_min. With 1/2 <= |y| <= 2, neither happens for min / eps^2 <= |x| <=
161// highest eps^2. Outside that interval x and p_hi are rescaled by a power of two, which keeps p_hi = fl(x y) while
162// p_hi is normal, and p_lo then takes the single rounding of fma(x, y, -p_hi).
163template <typename Scalar, std::enable_if_t<twoprod_full_range_uses_dekker<Scalar>::value, int> = 0>
164EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void twoprod_full_range_impl(const Scalar& x, const Scalar& y, Scalar& p_hi,
165 Scalar& p_lo) {
166 const Scalar eps2 = NumTraits<Scalar>::epsilon() * NumTraits<Scalar>::epsilon();
167 const Scalar abs_x = numext::abs(x);
168 Scalar hi = x * y;
169 pbarrier(hi);
170 p_hi = hi;
171 if (abs_x > NumTraits<Scalar>::highest() * eps2) {
172 p_lo = twoprod_low<Scalar, true>(Scalar(x * eps2), y, Scalar(hi * eps2)) / eps2;
173 } else if (abs_x < (std::numeric_limits<Scalar>::min)() / eps2) {
174 p_lo = twoprod_low<Scalar, true>(Scalar(x / eps2), y, Scalar(hi / eps2)) * eps2;
175 } else {
176 p_lo = twoprod_low<Scalar, true>(x, y, hi);
177 }
178}
179#endif
180
181template <typename Scalar, std::enable_if_t<!twoprod_full_range_uses_dekker<Scalar>::value, int> = 0>
182EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void twoprod_full_range_impl(const Scalar& x, const Scalar& y, Scalar& p_hi,
183 Scalar& p_lo) {
184 p_hi = x * y;
185 p_lo = twoprod_low_fma(x, y, p_hi);
186}
187
188// Declared in MathFunctions.h, for the scalar functions there.
189template <typename Scalar>
190EIGEN_DEVICE_FUNC void twoprod_full_range(const Scalar& x, const Scalar& y, Scalar& p_hi, Scalar& p_lo) {
191 twoprod_full_range_impl(x, y, p_hi, p_lo);
192}
193
194// This function implements the addition of two double word numbers
195// represented by {x_hi, x_lo} and {y_hi, y_lo}, with operands of either sign
196// and magnitude: Knuth's two-sum of the high parts is error-free, the low
197// parts are added to its error term, and the result is renormalized.
198// This is Algorithm 5 (SloppyDWPlusDW) from Joldes, Muller, & Popescu (2017),
199// "Tight and rigorous error bounds for basic building blocks of double-word
200// arithmetic", https://hal.science/hal-01351529: the error is a few u^2
201// relative to |x| + |y|, not to the sum, which may cancel.
202template <typename Packet>
203EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void twosum(const Packet& x_hi, const Packet& x_lo, const Packet& y_hi,
204 const Packet& y_lo, Packet& s_hi, Packet& s_lo) {
205 Packet s = padd(x_hi, y_hi);
206 Packet y_part = psub(s, x_hi);
207 Packet err = padd(psub(x_hi, psub(s, y_part)), psub(y_hi, y_part));
208 fast_twosum(s, padd(err, padd(x_lo, y_lo)), s_hi, s_lo);
209}
210
211// The difference {x_hi, x_lo} - {y_hi, y_lo} of two double word numbers,
212// the same algorithm as twosum with the sign of y folded into the operations.
213template <typename Packet>
214EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void twodiff(const Packet& x_hi, const Packet& x_lo, const Packet& y_hi,
215 const Packet& y_lo, Packet& s_hi, Packet& s_lo) {
216 Packet s = psub(x_hi, y_hi);
217 Packet y_part = psub(x_hi, s);
218 Packet err = psub(psub(x_hi, padd(s, y_part)), psub(y_hi, y_part));
219 fast_twosum(s, padd(err, psub(x_lo, y_lo)), s_hi, s_lo);
220}
221
222// This is a version of twosum for double word numbers,
223// which assumes that |x_hi| >= |y_hi|.
224template <typename Packet>
225EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void fast_twosum(const Packet& x_hi, const Packet& x_lo, const Packet& y_hi,
226 const Packet& y_lo, Packet& s_hi, Packet& s_lo) {
227 Packet r_hi, r_lo;
228 fast_twosum(x_hi, y_hi, r_hi, r_lo);
229 const Packet s = padd(padd(y_lo, r_lo), x_lo);
230 fast_twosum(r_hi, s, s_hi, s_lo);
231}
232
233// This is a version of twosum for adding a floating point number x to
234// double word number {y_hi, y_lo} number, with the assumption
235// that |x| >= |y_hi|.
236template <typename Packet>
237EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void fast_twosum(const Packet& x, const Packet& y_hi, const Packet& y_lo,
238 Packet& s_hi, Packet& s_lo) {
239 Packet r_hi, r_lo;
240 fast_twosum(x, y_hi, r_hi, r_lo);
241 const Packet s = padd(y_lo, r_lo);
242 fast_twosum(r_hi, s, s_hi, s_lo);
243}
244
245// This function implements the multiplication of a double word
246// number represented by {x_hi, x_lo} by a floating point number y.
247// It returns the result as a pair {p_hi, p_lo} such that
248// (x_hi + x_lo) * y = p_hi + p_lo holds with a relative error
249// of less than 2*2^{-2p}, where p is the number of significand bits
250// in the floating point type.
251// This is Algorithm 7 from Jean-Michel Muller, "Elementary Functions",
252// 3rd edition, Birkh\"auser, 2016.
253template <typename Packet>
254EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void twoprod(const Packet& x_hi, const Packet& x_lo, const Packet& y,
255 Packet& p_hi, Packet& p_lo) {
256 Packet c_hi, c_lo1;
257 twoprod(x_hi, y, c_hi, c_lo1);
258 const Packet c_lo2 = pmul(x_lo, y);
259 Packet t_hi, t_lo1;
260 fast_twosum(c_hi, c_lo2, t_hi, t_lo1);
261 const Packet t_lo2 = padd(t_lo1, c_lo1);
262 fast_twosum(t_hi, t_lo2, p_hi, p_lo);
263}
264
265// This function implements the multiplication of two double word
266// numbers represented by {x_hi, x_lo} and {y_hi, y_lo}.
267// For normalized inputs (x_hi = RN(x_hi + x_lo), likewise for y), the result
268// {p_hi, p_lo} has relative error < 5*u^2 for p-bit significands, u = 2^{-p}, p >= 8.
269// This assumes round-to-nearest, no overflow/underflow, an exact two-product
270// residual, and separately rounded operations outside that residual.
271// Each DW*FP product has relative error <= (3/2 + 4*u)*u^2: Joldes, Muller,
272// and Popescu (2017), "Tight and rigorous error bounds for basic building
273// blocks of double-word arithmetic", Theorem 4.1, https://hal.science/hal-01351529.
274// The final sum adds absolute error <= u^2*((3+3*u+u^2)*abs(p_hi_hi)
275// + (4+3*u+u^2)*abs(p_lo_hi)); using abs(y_lo) <= u*abs(y_hi) gives the bound above.
276template <typename Packet>
277EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void twoprod(const Packet& x_hi, const Packet& x_lo, const Packet& y_hi,
278 const Packet& y_lo, Packet& p_hi, Packet& p_lo) {
279 Packet p_hi_hi, p_hi_lo;
280 twoprod(x_hi, x_lo, y_hi, p_hi_hi, p_hi_lo);
281 Packet p_lo_hi, p_lo_lo;
282 twoprod(x_hi, x_lo, y_lo, p_lo_hi, p_lo_lo);
283 fast_twosum(p_hi_hi, p_hi_lo, p_lo_hi, p_lo_lo, p_hi, p_lo);
284}
285
286// This function implements the multiplication of two double word numbers
287// {x_hi, x_lo} and {y_hi, y_lo} at a lower cost than twoprod above: with
288// {c_hi, c_lo} = x_hi*y_hi exactly, it renormalizes c_hi + (c_lo + x_hi*y_lo +
289// x_lo*y_hi), dropping x_lo*y_lo. Scale x_hi and y_hi into [1, 2), so that
290// |x_lo|, |y_lo| <= u = 2^-p for p-bit significands.
291// Where pmadd is fused (is_fused_madd, and float and double scalars under
292// EIGEN_VECTORIZE_FMA), two pmadds accumulate the cross terms onto c_lo. If
293// x_hi*y_hi < 2, each rounds a value below 4*u, by at most 2*u^2, and the
294// dropped term is at most u^2, so the relative error is below 5*u^2 to first
295// order; if x_hi*y_hi >= 2 it is below 3.5*u^2. Measured maxima: 4.87*u^2 (float)
296// and 4.80*u^2 (double), 4.93*u^2 and 4.98*u^2 for squares.
297// Elsewhere the cross products are rounded and summed before c_lo is added:
298// Algorithm 10 (DWTimesDW1) of Joldes, Muller, & Popescu (2017),
299// https://hal.science/hal-01351529, measured at most 4.9997*u^2 (float) and
300// 4.94*u^2 (double), 4.00*u^2 for squares. Chaining unfused pmadds instead would
301// round each cross product as well, for up to 7*u^2 (measured 6.93*u^2).
302// Measured against an exact reference over 5*10^7 normalized operand pairs per
303// case plus a hill-climb search; round-to-nearest, no overflow or underflow.
304template <typename Packet>
305EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void fast_twoprod(const Packet& x_hi, const Packet& x_lo, const Packet& y_hi,
306 const Packet& y_lo, Packet& p_hi, Packet& p_lo) {
307 Packet c_hi, c_lo;
308 twoprod(x_hi, y_hi, c_hi, c_lo);
309#ifdef EIGEN_VECTORIZE_FMA
310 // Scalar float and double pmadd are numext::fma here, so scalars round like the packets.
311 constexpr bool kScalarFused = std::is_same<Packet, float>::value || std::is_same<Packet, double>::value;
312#else
313 constexpr bool kScalarFused = false;
314#endif
315 EIGEN_IF_CONSTEXPR (is_fused_madd<Packet>::value || kScalarFused) {
316 c_lo = pmadd(x_hi, y_lo, pmadd(x_lo, y_hi, c_lo));
317 } else {
318 c_lo = padd(c_lo, padd(pmul(x_hi, y_lo), pmul(x_lo, y_hi)));
319 }
320 fast_twosum(c_hi, c_lo, p_hi, p_lo);
321}
322
323// This function implements the division of double word {x_hi, x_lo}
324// by float y. This is Algorithm 15 from "Tight and rigorous error bounds
325// for basic building blocks of double-word arithmetic", Joldes, Muller, & Popescu,
326// 2017. https://hal.archives-ouvertes.fr/hal-01351529
327template <typename Packet>
328EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void doubleword_div_fp(const Packet& x_hi, const Packet& x_lo, const Packet& y,
329 Packet& z_hi, Packet& z_lo) {
330 const Packet t_hi = pdiv(x_hi, y);
331 Packet pi_hi, pi_lo;
332 twoprod(t_hi, y, pi_hi, pi_lo);
333 const Packet delta_hi = psub(x_hi, pi_hi);
334 const Packet delta_t = psub(delta_hi, pi_lo);
335 const Packet delta = padd(delta_t, x_lo);
336 const Packet t_lo = pdiv(delta, y);
337 fast_twosum(t_hi, t_lo, z_hi, z_lo);
338}
339
340} // end namespace internal
341} // end namespace Eigen
342
343#endif // EIGEN_ARCH_GENERIC_PACKET_MATH_DOUBLE_WORD_H