Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
MathFunctionsImpl.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2014 Pedro Gonnet (pedro.gonnet@gmail.com)
5// Copyright (C) 2016 Gael Guennebaud <gael.guennebaud@inria.fr>
6//
7// This Source Code Form is subject to the terms of the Mozilla
8// Public License v. 2.0. If a copy of the MPL was not distributed
9// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
10// SPDX-License-Identifier: MPL-2.0
11
12#ifndef EIGEN_MATHFUNCTIONSIMPL_H
13#define EIGEN_MATHFUNCTIONSIMPL_H
14
15// IWYU pragma: private
16#include "./InternalHeaderCheck.h"
17
18namespace Eigen {
19
20namespace internal {
21
39template <typename Packet, int Steps>
40struct generic_reciprocal_newton_step {
41 static_assert(Steps > 0, "Steps must be at least 1.");
42 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Packet run(const Packet& a, const Packet& approx_a_recip) {
43 using Scalar = typename unpacket_traits<Packet>::type;
44 const Packet one = pset1<Packet>(Scalar(1));
45 // Refine the approximation using one Newton-Raphson step:
46 // x_{i} = x_{i-1} * (2 - a * x_{i-1})
47 const Packet x = generic_reciprocal_newton_step<Packet, Steps - 1>::run(a, approx_a_recip);
48 const Packet tmp = pnmadd(a, x, one);
49 // Use two FMAs instead of FMA+FMUL to improve precision.
50 const Packet refined = pmadd(x, tmp, x);
51 // The step yields NaN when a is +/-0, +/-Inf or NaN, and NaN or 0 where the approximation flushed a denormal a or
52 // 1 / a to zero (x = +/-inf, or x = 0 for |a| > 1 / min). Divide in those lanes.
53 const Packet redo = pcmp_lt_or_nan(pabs(refined), pset1<Packet>((std::numeric_limits<Scalar>::denorm_min)()));
54 return predux_any(redo) ? pselect(redo, pdiv(one, a), refined) : refined;
55 }
56};
57
58template <typename Packet>
59struct generic_reciprocal_newton_step<Packet, 0> {
60 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Packet run(const Packet& /*unused*/, const Packet& approx_rsqrt) {
61 return approx_rsqrt;
62 }
63};
64
82template <typename Packet, int Steps>
83struct generic_rsqrt_newton_step {
84 static_assert(Steps > 0, "Steps must be at least 1.");
85 using Scalar = typename unpacket_traits<Packet>::type;
86 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Packet run(const Packet& a, const Packet& approx_rsqrt) {
87 const Scalar kMinusHalf = Scalar(-1) / Scalar(2);
88 const Packet cst_minus_half = pset1<Packet>(kMinusHalf);
89 const Packet cst_minus_one = pset1<Packet>(Scalar(-1));
90
91 Packet inv_sqrt = approx_rsqrt;
92 for (int step = 0; step < Steps; ++step) {
93 // Refine the approximation using one Newton-Raphson step:
94 // h_n = (x * inv_sqrt) * inv_sqrt - 1 (so that h_n is nearly 0).
95 // inv_sqrt = inv_sqrt - 0.5 * inv_sqrt * h_n
96 Packet r2 = pmul(a, inv_sqrt);
97 Packet half_r = pmul(inv_sqrt, cst_minus_half);
98 Packet h_n = pmadd(r2, inv_sqrt, cst_minus_one);
99 inv_sqrt = pmadd(half_r, h_n, inv_sqrt);
100 }
101
102 // If inv_sqrt is NaN, then either:
103 // 1) the input is NaN
104 // 2) zero and infinity were multiplied
105 // In either of these cases, return approx_rsqrt
106 return pselect(pisnan(inv_sqrt), approx_rsqrt, inv_sqrt);
107 }
108};
109
110template <typename Packet>
111struct generic_rsqrt_newton_step<Packet, 0> {
112 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Packet run(const Packet& /*unused*/, const Packet& approx_rsqrt) {
113 return approx_rsqrt;
114 }
115};
116
135template <typename Packet, int Steps = 1>
136struct generic_sqrt_newton_step {
137 static_assert(Steps > 0, "Steps must be at least 1.");
138
139 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE Packet run(const Packet& a, const Packet& approx_rsqrt) {
140 using Scalar = typename unpacket_traits<Packet>::type;
141 const Packet one_point_five = pset1<Packet>(Scalar(1.5));
142 const Packet minus_half = pset1<Packet>(Scalar(-0.5));
143 // If a is inf or zero, return a directly.
144 const Packet inf_mask = pcmp_eq(a, pset1<Packet>(NumTraits<Scalar>::infinity()));
145 const Packet return_a = por(pcmp_eq(a, pzero(a)), inf_mask);
146 // Do a single step of Newton's iteration for reciprocal square root:
147 // x_{n+1} = x_n * (1.5 + (-0.5 * x_n) * (a * x_n))).
148 // The Newton's step is computed this way to avoid over/under-flows.
149 Packet rsqrt = pmul(approx_rsqrt, pmadd(pmul(minus_half, approx_rsqrt), pmul(a, approx_rsqrt), one_point_five));
150 for (int step = 1; step < Steps; ++step) {
151 rsqrt = pmul(rsqrt, pmadd(pmul(minus_half, rsqrt), pmul(a, rsqrt), one_point_five));
152 }
153
154 // Return sqrt(x) = x * rsqrt(x) for non-zero finite positive arguments.
155 // Return a itself for 0 or +inf, NaN for negative arguments.
156 return pselect(return_a, a, pmul(a, rsqrt));
157 }
158};
159
160// sqrt(x^2 + y^2) for x, y >= 0. The generic version divides, so that no intermediate over- or underflows; it is
161// within 2 ulps. float and double have their own below.
162template <typename RealScalar, typename EnableIf = void>
163struct positive_real_hypot_impl {
164 EIGEN_DEVICE_FUNC static constexpr EIGEN_STRONG_INLINE RealScalar run(const RealScalar& x, const RealScalar& y) {
165 // IEEE IEC 60559 special cases.
166 if ((numext::isinf)(x) || (numext::isinf)(y)) return NumTraits<RealScalar>::infinity();
167 if ((numext::isnan)(x) || (numext::isnan)(y)) return NumTraits<RealScalar>::quiet_NaN();
168
169 RealScalar p = numext::maxi(x, y);
170 if (numext::is_exactly_zero(p)) return RealScalar(0);
171 RealScalar qp = numext::mini(y, x) / p;
172 return p * numext::sqrt<RealScalar>(RealScalar(1) + qp * qp);
173 }
174};
175
176// Host code only: GPU and SYCL device code keeps the generic version. Double precision is slow or missing there,
177// and neither of the two below has been run on a device. They are partial specializations so that a platform whose
178// types fail the condition falls back to the generic version. Doxygen cannot resolve their scope and stops.
179#if !defined(EIGEN_GPU_COMPILE_PHASE) && !defined(EIGEN_SYCL_DEVICE_ONLY) && !defined(EIGEN_PARSED_BY_DOXYGEN)
180// float in double precision, where neither square rounds, over- or underflows: the sum of squares is rounded once
181// before the square root, and the result is the correctly rounded one except for a few inputs in a billion.
182template <typename T>
183struct positive_real_hypot_impl<
184 T,
185 std::enable_if_t<std::is_same<T, float>::value && std::numeric_limits<float>::is_iec559 &&
186 std::numeric_limits<double>::is_iec559 &&
187 (std::numeric_limits<double>::digits >= 2 * std::numeric_limits<float>::digits + 2) &&
188 (std::numeric_limits<double>::max_exponent > 2 * std::numeric_limits<float>::max_exponent + 1)>> {
189 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE float run(const float& x, const float& y) {
190 // An infinite operand gives +inf even if the other one is NaN (IEC 60559). The operands are tested themselves:
191 // GCC 15 folds the same test away once it knows the result to be NaN (it takes both operands of a NaN sum to be
192 // NaN).
193 if (EIGEN_PREDICT_FALSE((numext::isinf)(x) || (numext::isinf)(y))) return NumTraits<float>::infinity();
194 const double dx = static_cast<double>(x);
195 const double dy = static_cast<double>(y);
196 const double xx = dx * dx;
197 return static_cast<float>(numext::sqrt(xx + dy * dy));
198 }
199};
200
201// double, as the square root of the sum of squares: no division, and one branch for operands whose squares neither
202// overflow nor lose bits to underflow. Where fma is an instruction the larger square is fused into the sum, so that
203// only the smaller square and the sum round before the square root, and the result is within 1.1 ulps; without it the
204// three roundings leave it within 1.2 ulps. Other operands, subnormal ones included, are scaled by a power of two.
205template <typename T>
206struct positive_real_hypot_impl<
207 T, std::enable_if_t<std::is_same<T, double>::value && std::numeric_limits<double>::is_iec559>> {
208 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE double run(const double& x, const double& y) {
209 // The larger and the smaller operand, in the form compilers turn into max and min instructions: a branch on x > y
210 // would be mispredicted half of the time for random operands.
211 const double p = x > y ? x : y;
212 const double q = y < x ? y : x;
213 // 2^-483 <= x + y <= 2^510 puts the larger operand in [2^-484, 2^510], where p^2 + q^2 is below 2^1022 and p^2 at
214 // least 2^-968, and excludes NaN and infinite operands. Testing the sum instead of p keeps the selection above
215 // free of branches with GCC.
216 const double sum = x + y;
217 if (EIGEN_PREDICT_TRUE(sum >= 4.004166190366202e-146 && sum <= 3.3519519824856493e+153)) {
218 return numext::sqrt(sum_of_squares(p, q, has_fast_fma<double>()));
219 }
220 return run_extreme(x, y);
221 }
222
223 private:
224 // Out of line, and without a second look at the sum: GCC (13 and 15 at least, with its default -ftrapping-math)
225 // threads the failed range test above into "sum < bound" for a NaN sum when the two share a function, which sent
226 // hypot(inf, NaN) down the scaled path.
227 EIGEN_DEVICE_FUNC static EIGEN_DONT_INLINE double run_extreme(double x, double y) {
228 // IEEE IEC 60559 special cases.
229 if ((numext::isinf)(x) || (numext::isinf)(y)) return NumTraits<double>::infinity();
230 if ((numext::isnan)(x) || (numext::isnan)(y)) return NumTraits<double>::quiet_NaN();
231 const double p = numext::maxi(x, y);
232 const double q = numext::mini(x, y);
233 if (numext::is_exactly_zero(p)) return 0.0;
234 // Scaled by 2^-514 above the range tested in run and by 2^600 below it, which brings subnormal operands into the
235 // normal range.
236 const bool large = p > 1.0;
237 const double scale = large ? 1.8645851828000517e-155 : 4.149515568880993e+180;
238 const double unscale = large ? 5.363123171977039e+154 : 2.409919865102884e-181;
239 return unscale * numext::sqrt(sum_of_squares(p * scale, q * scale, has_fast_fma<double>()));
240 }
241 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE double sum_of_squares(const double& p, const double& q, std::true_type) {
242 const double qq = q * q;
243 return numext::fma(p, p, qq);
244 }
245 EIGEN_DEVICE_FUNC static EIGEN_STRONG_INLINE double sum_of_squares(const double& p, const double& q,
246 std::false_type) {
247 const double pp = p * p;
248 const double qq = q * q;
249 return pp + qq;
250 }
251};
252#endif
253
254template <typename RealScalar>
255EIGEN_DEVICE_FUNC constexpr EIGEN_STRONG_INLINE RealScalar positive_real_hypot(const RealScalar& x,
256 const RealScalar& y) {
257 return positive_real_hypot_impl<RealScalar>::run(x, y);
258}
259
260template <typename Scalar>
261struct hypot_impl {
262 using RealScalar = typename NumTraits<Scalar>::Real;
263 static EIGEN_DEVICE_FUNC inline RealScalar run(const Scalar& x, const Scalar& y) {
264 return positive_real_hypot<RealScalar>(numext::abs(x), numext::abs(y));
265 }
266};
267
268template <typename ComplexT, bool Reciprocal>
269EIGEN_DEVICE_FUNC EIGEN_DONT_INLINE ComplexT complex_sqrt_extreme(const ComplexT& z) {
270 using T = typename NumTraits<ComplexT>::Real;
271 const T x = numext::real(z);
272 const T y = numext::imag(z);
273 const T zero = T(0);
274 const T inf = NumTraits<T>::infinity();
275 EIGEN_IF_CONSTEXPR (Reciprocal) {
276 if ((numext::isinf)(x) || (numext::isinf)(y)) return ComplexT(zero, numext::copysign<T>(zero, -y));
277 } else {
278 if ((numext::isinf)(y)) return ComplexT(inf, y);
279 if ((numext::isinf)(x)) {
280 const T other = (numext::isnan)(y) ? y : zero;
281 return x > zero ? ComplexT(inf, numext::copysign(other, y))
282 : ComplexT(numext::abs(other), numext::copysign(inf, y));
283 }
284 }
285 if ((numext::isnan)(x) || (numext::isnan)(y)) {
286 return ComplexT(NumTraits<T>::quiet_NaN(), NumTraits<T>::quiet_NaN());
287 }
288 if (numext::is_exactly_zero(x) && numext::is_exactly_zero(y)) {
289 return Reciprocal ? ComplexT(inf, NumTraits<T>::quiet_NaN()) : ComplexT(zero, y);
290 }
291
292 T ax = numext::abs(x);
293 T ay = numext::abs(y);
294 const T p = numext::maxi(ax, ay);
295 const T r = numext::mini(ax, ay) / p;
296 const T h = numext::sqrt(T(1) + r * r);
297 // Evaluate at z/p, restoring sqrt(p) only after taking the square root.
298 ax /= p;
299 ay /= p;
300 const T scale = numext::sqrt(p);
301 const T sum = ax + h;
302 const T w = numext::sqrt(T(0.5) * sum);
303 T major = w * scale;
304 T minor = zero;
305 EIGEN_IF_CONSTEXPR (Reciprocal) {
306 major = (w / h) / scale;
307 minor = (ay / sum) * major;
308 } else {
309 // Use the original y: normalizing z/p can underflow its smaller component.
310 minor = numext::abs(y) / (T(2) * major);
311 }
312 if (numext::is_exactly_zero(x)) minor = major;
313 const T imag_sign = Reciprocal ? -y : y;
314 return x < zero ? ComplexT(minor, numext::copysign(major, imag_sign))
315 : ComplexT(major, numext::copysign(minor, imag_sign));
316}
317
318template <typename ComplexT, bool Reciprocal>
319EIGEN_DEVICE_FUNC constexpr ComplexT complex_sqrt_impl(const ComplexT& z) {
320 using T = typename NumTraits<ComplexT>::Real;
321 const T x = numext::real(z);
322 const T y = numext::imag(z);
323 const T ax = numext::abs(x);
324 const T ay = numext::abs(y);
325 const bool real_larger = ax > ay;
326 const T p = real_larger ? ax : ay;
327 const T q = real_larger ? ay : ax;
328 // These bounds keep (|x| + |z|)/2 normal and finite. Using the same comparison
329 // for p and q preserves a NaN in either component.
330 if (EIGEN_PREDICT_FALSE(!(p > T(2) * (numext::numeric_limits<T>::min)() && p <= NumTraits<T>::highest() / T(4)))) {
331 return complex_sqrt_extreme<ComplexT, Reciprocal>(z);
332 }
333 const T r = q / p;
334 const T abs_z = p * numext::sqrt(T(1) + r * r);
335 const T sum = ax + abs_z;
336 const T w = numext::sqrt(T(0.5) * sum);
337 T major = w;
338 T minor = T(0);
339 EIGEN_IF_CONSTEXPR (Reciprocal) {
340 major = w / abs_z;
341 // |y|/(2*w*|z|) = (|y|/(|x| + |z|)) * (w/|z|), without a cubic-scale denominator.
342 minor = (ay / sum) * major;
343 } else {
344 minor = ay / (T(2) * w);
345 }
346 if (numext::is_exactly_zero(x)) minor = major;
347 const T imag_sign = Reciprocal ? -y : y;
348 return x < T(0) ? ComplexT(minor, numext::copysign(major, imag_sign))
349 : ComplexT(major, numext::copysign(minor, imag_sign));
350}
351
352// Principal square root, with the branch cut selected by the sign of the imaginary part.
353template <typename ComplexT>
354EIGEN_DEVICE_FUNC constexpr ComplexT complex_sqrt(const ComplexT& z) {
355 return complex_sqrt_impl<ComplexT, false>(z);
356}
357
358template <typename ComplexT>
359EIGEN_DEVICE_FUNC constexpr ComplexT complex_rsqrt(const ComplexT& z) {
360 return complex_sqrt_impl<ComplexT, true>(z);
361}
362
363template <typename ComplexT>
364EIGEN_DEVICE_FUNC constexpr ComplexT complex_log(const ComplexT& z) {
365 // Computes complex log.
366 using T = typename NumTraits<ComplexT>::Real;
367 T a = numext::abs(z);
368 T b = numext::atan2(z.imag(), z.real());
369 // log|z| is finite where |z| itself overflows or rounds to a subnormal: scale z exactly by a power of two first.
370 if (EIGEN_PREDICT_FALSE((numext::isinf)(a) && (numext::isfinite)(z.real()) && (numext::isfinite)(z.imag()))) {
371 const T half = T(0.5);
372 return ComplexT(numext::log(numext::abs(ComplexT(z.real() * half, z.imag() * half))) + T(EIGEN_LN2), b);
373 }
374 if (EIGEN_PREDICT_FALSE(a < (numext::numeric_limits<T>::min)() && !numext::is_exactly_zero(a))) {
375 const T eps = NumTraits<T>::epsilon();
376 return ComplexT(numext::log(numext::abs(ComplexT(z.real() / eps, z.imag() / eps))) + numext::log(eps), b);
377 }
378 return ComplexT(numext::log(a), b);
379}
380
381// log2|z| + i arg(z) log2(e), scaled as in complex_log. The real part comes from log2, which is exact where |z| is a
382// power of two; log2(e) log|z| can be an ulp off there.
383template <typename ComplexT>
384EIGEN_DEVICE_FUNC ComplexT complex_log2(const ComplexT& z) {
385 using T = typename NumTraits<ComplexT>::Real;
386 const T a = numext::abs(z);
387 const T b = T(EIGEN_LOG2E) * numext::atan2(z.imag(), z.real());
388 if (EIGEN_PREDICT_FALSE((numext::isinf)(a) && (numext::isfinite)(z.real()) && (numext::isfinite)(z.imag()))) {
389 const T half = T(0.5);
390 return ComplexT(numext::log2(numext::abs(ComplexT(z.real() * half, z.imag() * half))) + T(1), b);
391 }
392 if (EIGEN_PREDICT_FALSE(a < (numext::numeric_limits<T>::min)() && !numext::is_exactly_zero(a))) {
393 const T eps = NumTraits<T>::epsilon();
394 return ComplexT(numext::log2(numext::abs(ComplexT(z.real() / eps, z.imag() / eps))) + numext::log2(eps), b);
395 }
396 return ComplexT(numext::log2(a), b);
397}
398
399} // end namespace internal
400
401} // end namespace Eigen
402
403#endif // EIGEN_MATHFUNCTIONSIMPL_H