Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
ApproxComparisons.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2006-2008 Benoit Jacob <jacob.benoit.1@gmail.com>
5// Copyright (C) 2008 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_APPROX_COMPARISONS_H
13#define EIGEN_APPROX_COMPARISONS_H
14
15// IWYU pragma: private
16#include "./InternalHeaderCheck.h"
17
18namespace Eigen {
19
20namespace internal {
21
22// Keep custom scalars on the algebraic path: exponent scaling requires binary floating-point arithmetic.
23template <typename Scalar>
24struct use_scaled_comparison
25 : bool_constant<(std::is_floating_point<Scalar>::value && std::numeric_limits<Scalar>::radix == 2) ||
26 std::is_same<Scalar, half>::value || std::is_same<Scalar, bfloat16>::value> {};
27
28template <typename RealScalar>
29struct use_scaled_comparison<std::complex<RealScalar>> : use_scaled_comparison<RealScalar> {};
30
31// A nonnegative magnitude fraction * 2^exponent, including norms larger than the scalar range. Positive finite
32// magnitudes order lexicographically by (exponent, fraction), the member order.
33template <typename RealScalar>
34struct comparison_magnitude {
35 int exponent = 0;
36 RealScalar fraction;
37
38 EIGEN_DEVICE_FUNC explicit comparison_magnitude(const RealScalar& value) : fraction(value) {
39 if (value > RealScalar(0) && value <= NumTraits<RealScalar>::highest()) {
40 EIGEN_USING_STD(frexp);
41 fraction = frexp(value, &exponent);
42 }
43 }
44
45 template <typename OtherRealScalar>
46 EIGEN_DEVICE_FUNC explicit comparison_magnitude(const comparison_magnitude<OtherRealScalar>& value)
47 : exponent(value.exponent), fraction(RealScalar(value.fraction)) {}
48
49 EIGEN_DEVICE_FUNC void multiply(const RealScalar& value) { multiply(comparison_magnitude(value)); }
50
51 EIGEN_DEVICE_FUNC void multiply(const comparison_magnitude& factor) {
52 const comparison_magnitude product(fraction * factor.fraction);
53 fraction = product.fraction;
54 exponent += factor.exponent + product.exponent;
55 }
56
57 EIGEN_DEVICE_FUNC bool isFinite() const { return fraction <= RealScalar(1); }
58};
59
60template <typename RealScalar>
61EIGEN_DEVICE_FUNC bool operator<=(const comparison_magnitude<RealScalar>& x,
62 const comparison_magnitude<RealScalar>& y) {
63 if (!x.isFinite()) return false;
64 // Zero and non-finite magnitudes carry no exponent.
65 if (!y.isFinite() || x.fraction == RealScalar(0) || y.fraction == RealScalar(0)) return x.fraction <= y.fraction;
66 return x.exponent < y.exponent || (x.exponent == y.exponent && x.fraction <= y.fraction);
67}
68
69template <typename RealScalar, typename OtherRealScalar>
70EIGEN_DEVICE_FUNC bool operator<=(const comparison_magnitude<RealScalar>& x,
71 const comparison_magnitude<OtherRealScalar>& y) {
72 using Common = std::common_type_t<RealScalar, OtherRealScalar>;
73 return comparison_magnitude<Common>(x) <= comparison_magnitude<Common>(y);
74}
75
76// Types whose data(), rowStride() and colStride() address every coefficient. DirectAccessBit alone does not promise
77// this: a single-row IndexedView of a column-major matrix and the RealView of a strided complex block report strides
78// that do not.
79template <typename X>
80struct scaled_comparison_viewable : std::false_type {};
81
82template <typename Scalar, int Rows, int Cols, int Options, int MaxRows, int MaxCols>
83struct scaled_comparison_viewable<Matrix<Scalar, Rows, Cols, Options, MaxRows, MaxCols>> : std::true_type {};
84
85template <typename Scalar, int Rows, int Cols, int Options, int MaxRows, int MaxCols>
86struct scaled_comparison_viewable<Array<Scalar, Rows, Cols, Options, MaxRows, MaxCols>> : std::true_type {};
87
88template <typename PlainObjectType, int Options, typename StrideType>
89struct scaled_comparison_viewable<Map<PlainObjectType, Options, StrideType>> : std::true_type {};
90
91template <typename PlainObjectType, int Options, typename StrideType>
92struct scaled_comparison_viewable<Ref<PlainObjectType, Options, StrideType>> : std::true_type {};
93
94template <typename XprType, int BlockRows, int BlockCols, bool InnerPanel>
95struct scaled_comparison_viewable<Block<XprType, BlockRows, BlockCols, InnerPanel>>
96 : scaled_comparison_viewable<std::remove_const_t<XprType>> {};
97
98template <typename XprType>
99struct scaled_comparison_viewable<Transpose<XprType>> : scaled_comparison_viewable<std::remove_const_t<XprType>> {};
100
101template <typename XprType>
102struct scaled_comparison_viewable<ArrayWrapper<XprType>> : scaled_comparison_viewable<std::remove_const_t<XprType>> {};
103
104template <typename XprType>
105struct scaled_comparison_viewable<MatrixWrapper<XprType>> : scaled_comparison_viewable<std::remove_const_t<XprType>> {};
106
107// The scaled path reduces each operand several times, so it runs on at most three view types per scalar type rather
108// than being instantiated for every operand expression. A viewable operand with direct access is viewed in place,
109// keeping packet access when its inner stride is one; any other operand, including a lazy expression or a shape that
110// hides operator*(Scalar) as Homogeneous does, is evaluated first, which allocates only for dynamic sizes and for
111// fixed sizes above EIGEN_STACK_ALLOCATION_LIMIT.
112template <typename X, bool DirectAccess = has_direct_access<X>::value && scaled_comparison_viewable<X>::value,
113 bool UnitInnerStride = inner_stride_at_compile_time<X>::value == 1>
114struct scaled_comparison_operand {
115 using View =
116 Map<const Matrix<typename X::Scalar, Dynamic, Dynamic, X::IsRowMajor ? RowMajor : ColMajor>, 0, OuterStride<>>;
117 EIGEN_DEVICE_FUNC explicit scaled_comparison_operand(const X& x)
118 : view(x.data(), x.rows(), x.cols(), OuterStride<>(x.outerStride())) {}
119 View view;
120};
121
122template <typename X>
123struct scaled_comparison_operand<X, true, false> {
124 using View = Map<const Matrix<typename X::Scalar, Dynamic, Dynamic>, 0, Stride<Dynamic, Dynamic>>;
125 EIGEN_DEVICE_FUNC explicit scaled_comparison_operand(const X& x)
126 : view(x.data(), x.rows(), x.cols(), Stride<Dynamic, Dynamic>(x.colStride(), x.rowStride())) {}
127 View view;
128};
129
130template <typename X, bool UnitInnerStride>
131struct scaled_comparison_operand<X, false, UnitInnerStride> {
132 // A fixed capacity the stack limit would reject makes the comparison fail to compile for an operand the caller
133 // never stores, so the temporary takes it only where DenseStorage accepts it.
134 static constexpr bool FixedCapacity =
135 EIGEN_STACK_ALLOCATION_LIMIT == 0 ||
136 (X::MaxSizeAtCompileTime != Dynamic &&
137 std::ptrdiff_t(X::MaxSizeAtCompileTime) * std::ptrdiff_t(sizeof(typename X::Scalar)) <=
138 std::ptrdiff_t(EIGEN_STACK_ALLOCATION_LIMIT));
139 // Column-major unless it holds at most one row, where Matrix requires row-major storage.
140 using Plain =
141 Matrix<typename X::Scalar, Dynamic, Dynamic,
142 X::MaxRowsAtCompileTime == 1 && X::MaxColsAtCompileTime != 1 ? RowMajor : ColMajor,
143 FixedCapacity ? X::MaxRowsAtCompileTime : Dynamic, FixedCapacity ? X::MaxColsAtCompileTime : Dynamic>;
144 using View = typename scaled_comparison_operand<Plain>::View;
145 EIGEN_DEVICE_FUNC explicit scaled_comparison_operand(const X& x)
146 : value(x.matrix()), view(scaled_comparison_operand<Plain>(value).view) {}
147 Plain value;
148 View view;
149};
150
151template <typename Components>
152EIGEN_DEVICE_FUNC typename Components::Scalar scaled_comparison_max_coeff(const Components& components) {
153 using RealScalar = typename Components::Scalar;
154 if (components.size() == 0) return RealScalar(0);
155 return safe_scaling<RealScalar>::recover_flushed_max_coeff(components,
156 components.cwiseAbs().template maxCoeff<PropagateNaN>());
157}
158
159template <typename Derived>
160EIGEN_DEVICE_FUNC comparison_magnitude<typename stable_norm_accumulator<typename Derived::RealScalar>::type>
161scaled_comparison_norm_impl(const MatrixBase<Derived>& matrix) {
162 using RealScalar = typename stable_norm_accumulator<typename Derived::RealScalar>::type;
163 const auto& realComponents = matrix.realView();
164 const auto& components = realComponents.template cast<RealScalar>();
165 const RealScalar scale = scaled_comparison_max_coeff(components);
166 // Classify first so NaNs do not reach the ordered comparison.
167 if (!(numext::isfinite)(scale) || !(scale > RealScalar(0))) return comparison_magnitude<RealScalar>(scale);
168 RealScalar squaredNorm = RealScalar(0);
169 const auto factors = safe_scaling<RealScalar>::with_scaled(
170 components, scale, [&](const auto& scaled) { squaredNorm = scaled.squaredNorm(); });
171 comparison_magnitude<RealScalar> result(numext::sqrt(squaredNorm));
172 result.multiply(factors.scale);
173 return result;
174}
175
176template <typename X, typename Y>
177EIGEN_DEVICE_FUNC comparison_magnitude<typename stable_norm_accumulator<typename X::RealScalar>::type>
178scaled_comparison_distance_impl(const MatrixBase<X>& matrixX, const MatrixBase<Y>& matrixY) {
179 using Accumulator = typename stable_norm_accumulator<typename X::RealScalar>::type;
180 using WideScalar =
181 std::conditional_t<NumTraits<typename X::Scalar>::IsComplex || NumTraits<typename Y::Scalar>::IsComplex,
182 std::complex<Accumulator>, Accumulator>;
183 const auto& wideX = matrixX.template cast<WideScalar>();
184 const auto& wideY = matrixY.template cast<WideScalar>();
185 // FTZ flushes a subnormal difference of normal operands. Scaling a maximum M < 1 up by a power of two first loses
186 // only differences below M * min; scaling larger operands down could underflow their small components.
187 const Accumulator maxCoeff = numext::mini(
188 Accumulator(1),
189 numext::maxi(scaled_comparison_max_coeff(wideX.realView()), scaled_comparison_max_coeff(wideY.realView())));
190 const safe_scaling_factors<Accumulator> factors = supports_power_of_two_scaling<Accumulator>::value
191 ? safe_scaling<Accumulator>::compute_floor_factors(maxCoeff)
192 : safe_scaling_factors<Accumulator>();
193 // Both calls share one expression type, so scaled_comparison_norm_impl is instantiated once.
194 auto difference = scaled_comparison_norm_impl(wideX * factors.invScale - wideY * factors.invScale);
195 if (!difference.isFinite()) {
196 // Finite operands can overflow on subtraction; halving first keeps every component representable.
197 const Accumulator halfInvScale = factors.invScale * Accumulator(0.5);
198 difference = scaled_comparison_norm_impl(wideX * halfInvScale - wideY * halfInvScale);
199 difference.multiply(Accumulator(2));
200 }
201 difference.multiply(factors.scale);
202 return difference;
203}
204
205template <typename Derived>
206EIGEN_DEVICE_FUNC comparison_magnitude<typename stable_norm_accumulator<typename Derived::RealScalar>::type>
207scaled_comparison_norm(const Derived& x) {
208 return scaled_comparison_norm_impl(scaled_comparison_operand<Derived>(x).view);
209}
210
211template <typename X, typename Y>
212EIGEN_DEVICE_FUNC comparison_magnitude<typename stable_norm_accumulator<typename X::RealScalar>::type>
213scaled_comparison_distance(const X& x, const Y& y) {
214 return scaled_comparison_distance_impl(scaled_comparison_operand<X>(x).view, scaled_comparison_operand<Y>(y).view);
215}
216
217// Coefficients widened to the stable-norm accumulator, in which ordinary comparisons square and sum. The cast is the
218// identity for float and double; half and bfloat16 widen exactly to float, where no half square underflows.
219template <typename X>
220using approx_comparison_wide_t =
221 std::conditional_t<NumTraits<typename X::Scalar>::IsComplex,
222 std::complex<typename stable_norm_accumulator<typename X::RealScalar>::type>,
223 typename stable_norm_accumulator<typename X::RealScalar>::type>;
224
225template <typename Scalar, bool = use_scaled_comparison<Scalar>::value>
226struct approx_comparison_impl {
227 using RealScalar = typename NumTraits<Scalar>::Real;
228
229 template <typename X, typename Y>
230 EIGEN_DEVICE_FUNC static bool isApprox(const X& x, const Y& y, const RealScalar& prec) {
231 return (x.matrix() - y.matrix()).cwiseAbs2().sum() <=
232 prec * prec * numext::mini(x.cwiseAbs2().sum(), y.cwiseAbs2().sum());
233 }
234
235 template <typename X, typename Y>
236 EIGEN_DEVICE_FUNC static bool isMuchSmallerThan(const X& x, const Y& y, const RealScalar& prec) {
237 return x.cwiseAbs2().sum() <= numext::abs2(prec) * y.cwiseAbs2().sum();
238 }
239
240 template <typename X>
241 EIGEN_DEVICE_FUNC static bool isMuchSmallerThan(const X& x, const RealScalar& y, const RealScalar& prec) {
242 return x.cwiseAbs2().sum() <= numext::abs2(prec * y);
243 }
244};
245
246template <typename Scalar>
247struct approx_comparison_impl<Scalar, true> {
248 using RealScalar = typename NumTraits<Scalar>::Real;
249 using Accumulator = typename stable_norm_accumulator<RealScalar>::type;
250 template <typename Y>
251 using CommonAccumulator =
252 std::common_type_t<Accumulator, typename stable_norm_accumulator<typename Y::RealScalar>::type>;
253
254 template <typename ValueScalar>
255 EIGEN_DEVICE_FUNC static typename stable_norm_accumulator<ValueScalar>::type squared_norm_lower_bound(Index size) {
256 using ValueAccumulator = typename stable_norm_accumulator<ValueScalar>::type;
257 // Squares accumulate in ValueAccumulator; below n * min / epsilon, flushed squares can affect the comparison.
258 return stable_normalization_normal_min<ValueAccumulator, ValueAccumulator>::run() /
259 NumTraits<ValueAccumulator>::epsilon() * ValueAccumulator(size);
260 }
261
262 template <typename BoundScalar>
263 EIGEN_DEVICE_FUNC static bool safe_squared_norm(const BoundScalar& value, Index size) {
264 using Common = std::common_type_t<Accumulator, BoundScalar>;
265 return Common(value) >= Common(squared_norm_lower_bound<RealScalar>(size)) &&
266 Common(value) <= Common(NumTraits<Accumulator>::highest());
267 }
268
269 template <typename X, typename Y>
270 EIGEN_DEVICE_FUNC static bool isApprox(const X& x, const Y& y, const RealScalar& prec) {
271 // Widening must not admit operands that cannot be subtracted, such as half and float.
272 EIGEN_CHECK_BINARY_COMPATIBILITY(scalar_difference_op<typename X::Scalar EIGEN_COMMA typename Y::Scalar>,
273 typename X::Scalar, typename Y::Scalar)
274 const auto& wideX = x.template cast<approx_comparison_wide_t<X>>();
275 const auto& wideY = y.template cast<approx_comparison_wide_t<Y>>();
276 const Accumulator x2 = wideX.cwiseAbs2().sum();
277 const Accumulator y2 = wideY.cwiseAbs2().sum();
278 const Accumulator minimum = numext::mini(x2, y2);
279 const Accumulator precision2 = Accumulator(prec) * Accumulator(prec);
280 const Accumulator bound = precision2 * minimum;
281 // Only the smaller norm enters the bound; overflow of the larger norm is harmless.
282 if (safe_squared_norm(bound, x.size()) && minimum >= squared_norm_lower_bound<RealScalar>(x.size()) &&
283 precision2 >= squared_norm_lower_bound<RealScalar>(1))
284 return (wideX.matrix() - wideY.matrix()).cwiseAbs2().sum() <= bound;
285
286 return isApprox_scaled(x, y, prec);
287 }
288
289 template <typename X, typename Y>
290 EIGEN_DEVICE_FUNC static bool isMuchSmallerThan(const X& x, const Y& y, const RealScalar& prec) {
291 using Common = CommonAccumulator<Y>;
292 typename nested_eval<X, 2>::type nested(x);
293 typename nested_eval<Y, 2>::type otherNested(y);
294 const Accumulator x2 = nested.template cast<approx_comparison_wide_t<X>>().cwiseAbs2().sum();
295 const auto y2 = otherNested.template cast<approx_comparison_wide_t<Y>>().cwiseAbs2().sum();
296 const Accumulator precision2 = numext::abs2(Accumulator(prec));
297 const Common bound = Common(precision2) * Common(y2);
298 // A finite bound above the flushing error makes overflow/underflow of x2 harmless.
299 if (safe_squared_norm(bound, x.size()) &&
300 Common(y2) >= Common(squared_norm_lower_bound<typename Y::RealScalar>(y.size())) &&
301 precision2 >= squared_norm_lower_bound<RealScalar>(1))
302 return Common(x2) <= bound;
303 return isMuchSmallerThan_scaled(nested, otherNested, prec);
304 }
305
306 template <typename X>
307 EIGEN_DEVICE_FUNC static bool isMuchSmallerThan(const X& x, const RealScalar& y, const RealScalar& prec) {
308 typename nested_eval<X, 2>::type nested(x);
309 const Accumulator x2 = nested.template cast<approx_comparison_wide_t<X>>().cwiseAbs2().sum();
310 const Accumulator bound = numext::abs2(Accumulator(prec) * Accumulator(y));
311 if (safe_squared_norm(bound, x.size())) return x2 <= bound;
312 return isMuchSmallerThan_scaled(nested, y, prec);
313 }
314
315 private:
316 // Keep exponent scaling from inhibiting inlining of ordinary comparisons.
317 template <typename X, typename Y>
318 EIGEN_DEVICE_FUNC static EIGEN_DONT_INLINE bool isApprox_scaled(const X& xExpr, const Y& yExpr,
319 const RealScalar& prec) {
320 const scaled_comparison_operand<X> x(xExpr);
321 const scaled_comparison_operand<Y> y(yExpr);
322 const auto nx = scaled_comparison_norm_impl(x.view);
323 const auto ny = scaled_comparison_norm_impl(y.view);
324 if (!nx.isFinite() || !ny.isFinite()) return false;
325 auto tolerance = nx <= ny ? nx : ny;
326 tolerance.multiply(numext::abs(Accumulator(prec)));
327 return scaled_comparison_distance_impl(x.view, y.view) <= tolerance;
328 }
329
330 template <typename X, typename Y>
331 EIGEN_DEVICE_FUNC static EIGEN_DONT_INLINE bool isMuchSmallerThan_scaled(const X& x, const Y& y,
332 const RealScalar& prec) {
333 using Common = CommonAccumulator<Y>;
334 comparison_magnitude<Common> tolerance(scaled_comparison_norm(y));
335 tolerance.multiply(numext::abs(Common(prec)));
336 return scaled_comparison_norm(x) <= tolerance;
337 }
338
339 template <typename X>
340 EIGEN_DEVICE_FUNC static EIGEN_DONT_INLINE bool isMuchSmallerThan_scaled(const X& x, const RealScalar& y,
341 const RealScalar& prec) {
342 comparison_magnitude<Accumulator> tolerance(numext::abs(Accumulator(y)));
343 tolerance.multiply(numext::abs(Accumulator(prec)));
344 return scaled_comparison_norm(x) <= tolerance;
345 }
346};
347
348// Exponent scaling needs binary floating-point on both sides.
349template <typename Derived, typename OtherDerived>
350using approx_comparison_impl_t =
351 approx_comparison_impl<typename Derived::Scalar, use_scaled_comparison<typename Derived::Scalar>::value &&
352 use_scaled_comparison<typename OtherDerived::Scalar>::value>;
353
354template <typename Derived, typename OtherDerived, bool is_integer = NumTraits<typename Derived::Scalar>::IsInteger>
355struct isApprox_selector {
356 EIGEN_DEVICE_FUNC static bool run(const Derived& x, const OtherDerived& y, const typename Derived::RealScalar& prec) {
357 typename internal::nested_eval<Derived, 2>::type nested(x);
358 typename internal::nested_eval<OtherDerived, 2>::type otherNested(y);
359 return approx_comparison_impl_t<Derived, OtherDerived>::isApprox(nested, otherNested, prec);
360 }
361};
362
363template <typename Derived, typename OtherDerived>
364struct isApprox_selector<Derived, OtherDerived, true> {
365 EIGEN_DEVICE_FUNC static bool run(const Derived& x, const OtherDerived& y, const typename Derived::RealScalar&) {
366 return x.matrix() == y.matrix();
367 }
368};
369
370template <typename Derived, typename OtherDerived, bool is_integer = NumTraits<typename Derived::Scalar>::IsInteger>
371struct isMuchSmallerThan_object_selector {
372 EIGEN_DEVICE_FUNC static bool run(const Derived& x, const OtherDerived& y, const typename Derived::RealScalar& prec) {
373 return approx_comparison_impl_t<Derived, OtherDerived>::isMuchSmallerThan(x, y, prec);
374 }
375};
376
377template <typename Derived, typename OtherDerived>
378struct isMuchSmallerThan_object_selector<Derived, OtherDerived, true> {
379 EIGEN_DEVICE_FUNC static bool run(const Derived& x, const OtherDerived&, const typename Derived::RealScalar&) {
380 return x.matrix() == Derived::Zero(x.rows(), x.cols()).matrix();
381 }
382};
383
384template <typename Derived, bool is_integer = NumTraits<typename Derived::Scalar>::IsInteger>
385struct isMuchSmallerThan_scalar_selector {
386 EIGEN_DEVICE_FUNC static bool run(const Derived& x, const typename Derived::RealScalar& y,
387 const typename Derived::RealScalar& prec) {
388 return approx_comparison_impl<typename Derived::Scalar>::isMuchSmallerThan(x, y, prec);
389 }
390};
391
392template <typename Derived>
393struct isMuchSmallerThan_scalar_selector<Derived, true>
394 : isMuchSmallerThan_object_selector<Derived, typename Derived::RealScalar, true> {};
395
396// a b = fraction 2^exponent, with the frexp significands of a and b multiplied in [1/4, 1): a b rounded as if the
397// exponent range were unbounded. Zero if a or b is.
398template <typename RealScalar>
399struct unbounded_product {
400 EIGEN_DEVICE_FUNC unbounded_product(const RealScalar& a, const RealScalar& b) {
401 int exponentA = 0, exponentB = 0;
402 const RealScalar fractionA = frexp_preserving_subnormals(a, exponentA);
403 const RealScalar fractionB = frexp_preserving_subnormals(b, exponentB);
404 fraction = fractionA * fractionB;
405 exponent = exponentA + exponentB;
406 }
407
408 // a b 2^-maxExponent, exact unless it falls below the normal range.
409 EIGEN_DEVICE_FUNC RealScalar scaled(int maxExponent) const {
410 return ldexp_preserving_subnormals(fraction, exponent - maxExponent);
411 }
412
413 RealScalar fraction;
414 int exponent;
415};
416
417// |<v, w>| <= prec |v| |w|. The squared form, |<v, w>|^2 <= prec^2 |v|^2 |w|^2, is homogeneous of degree four, so for
418// |v_i| above ~4e9 or below ~1e-11 in float both sides overflow to inf <= inf or underflow to 0 <= 0. Scalars that
419// isApprox() does not scale, integers, custom complex and exact custom types included, keep it: it needs no sqrt.
420template <typename Derived, typename OtherDerived,
421 bool Scaled = use_scaled_comparison<typename Derived::Scalar>::value &&
422 use_scaled_comparison<typename OtherDerived::Scalar>::value>
423struct is_orthogonal_impl {
424 template <typename RealScalar>
425 static bool run(const Derived& v, const OtherDerived& w, const RealScalar& prec) {
426 typename nested_eval<Derived, 2>::type nested(v);
427 typename nested_eval<OtherDerived, 2>::type otherNested(w);
428 return numext::abs2(nested.dot(otherNested)) <= prec * prec * nested.squaredNorm() * otherNested.squaredNorm();
429 }
430};
431
432// Unsquared from the coefficients while |v|^2, |w|^2 and |<v, w>| are in range; otherwise with every product of
433// components rounded at its own exponent, so that neither an exact cancellation nor a nonzero product outside the
434// exponent range is lost.
435template <typename Derived, typename OtherDerived>
436struct is_orthogonal_impl<Derived, OtherDerived, true> {
437 // half and bfloat16 are compared in float, which holds them exactly.
438 using Accumulator = std::common_type_t<
439 typename stable_norm_accumulator<typename NumTraits<typename Derived::Scalar>::Real>::type,
440 typename stable_norm_accumulator<typename NumTraits<typename OtherDerived::Scalar>::Real>::type>;
441 template <typename Xpr>
442 using Wide = std::conditional_t<NumTraits<typename Xpr::Scalar>::IsComplex, std::complex<Accumulator>, Accumulator>;
443
444 template <typename RealScalar>
445 static bool run(const Derived& v, const OtherDerived& w, const RealScalar& prec) {
446 // Widening must not admit operands that dot() rejects, such as float and double.
447 EIGEN_CHECK_BINARY_COMPATIBILITY(
448 scalar_conj_product_op<typename Derived::Scalar EIGEN_COMMA typename OtherDerived::Scalar>,
449 typename Derived::Scalar, typename OtherDerived::Scalar)
450 typename nested_eval<Derived, 2>::type nested(v);
451 typename nested_eval<OtherDerived, 2>::type otherNested(w);
452 const auto& wideV = nested.template cast<Wide<Derived>>();
453 const auto& wideW = otherNested.template cast<Wide<OtherDerived>>();
454 const Accumulator v2 = wideV.squaredNorm();
455 const Accumulator w2 = wideW.squaredNorm();
456 // Each flushed product, square or partial sum moves |v|^2, |w|^2 or <v, w> by less than min, and a complex
457 // coefficient takes up to four per component: less than 8n min in all, at most epsilon x for any x >= lower.
458 const Accumulator lower = Accumulator(8) * Accumulator(v.size()) *
459 stable_normalization_normal_min<Accumulator, Accumulator>::run() /
460 NumTraits<Accumulator>::epsilon();
461 const Accumulator highest = NumTraits<Accumulator>::highest();
462 if (v2 >= lower && v2 <= highest && w2 >= lower && w2 <= highest) {
463 const Accumulator absDot = numext::abs(wideV.dot(wideW));
464 const Accumulator bound = Accumulator(prec) * (numext::sqrt(v2) * numext::sqrt(w2));
465 // |<v, w>| <= |v| |w| <= highest up to rounding. Below lower, underflow may have hidden all of <v, w>, but
466 // |<v, w>| < 2 lower.
467 if (absDot >= lower && absDot <= highest) return absDot <= bound;
468 if (absDot < lower && bound >= Accumulator(2) * lower) return true;
469 }
470 return run_unbounded(wideV, wideW, Accumulator(prec));
471 }
472
473 private:
474 using Product = unbounded_product<Accumulator>;
475
476 // func(ac, bd, ad, bc) for each conj(x_k) y_k = (ac + bd) + i (ad - bc), where x_k = a + ib and y_k = c + id.
477 template <typename X, typename Y, typename Func>
478 static void for_each_product(const X& x, const Y& y, Func func) {
479 const evaluator<X> xCoeffs(x);
480 const evaluator<Y> yCoeffs(y);
481 for (Index k = 0; k < x.size(); ++k) {
482 const Accumulator a = numext::real(xCoeffs.coeff(k)), b = numext::imag(xCoeffs.coeff(k));
483 const Accumulator c = numext::real(yCoeffs.coeff(k)), d = numext::imag(yCoeffs.coeff(k));
484 func(Product(a, c), Product(b, d), Product(a, d), Product(b, c));
485 }
486 }
487
488 // |<x, y>| from the products scaled by 2^-E, E the largest product exponent: the largest term is at least 1/4, and
489 // only a term that falls below the normal range, far under an ulp of it, rounds again.
490 template <typename X, typename Y>
491 static comparison_magnitude<Accumulator> unbounded_dot_magnitude(const X& x, const Y& y) {
492 bool nonzero = false;
493 int maxExponent = 0;
494 const auto include = [&](const Product& product) {
495 if (product.fraction == Accumulator(0)) return;
496 maxExponent = nonzero ? numext::maxi(maxExponent, product.exponent) : product.exponent;
497 nonzero = true;
498 };
499 for_each_product(x, y, [&](const Product& ac, const Product& bd, const Product& ad, const Product& bc) {
500 include(ac);
501 include(bd);
502 include(ad);
503 include(bc);
504 });
505 if (!nonzero) return comparison_magnitude<Accumulator>(Accumulator(0));
506 Accumulator re(0), im(0);
507 for_each_product(x, y, [&](const Product& ac, const Product& bd, const Product& ad, const Product& bc) {
508 re += ac.scaled(maxExponent) + bd.scaled(maxExponent);
509 im += ad.scaled(maxExponent) - bc.scaled(maxExponent);
510 });
511 comparison_magnitude<Accumulator> magnitude(numext::hypot(re, im));
512 magnitude.exponent += maxExponent;
513 return magnitude;
514 }
515
516 // Keep the exponent arithmetic from inhibiting inlining of ordinary comparisons.
517 template <typename V, typename W>
518 static EIGEN_DONT_INLINE bool run_unbounded(const V& v, const W& w, const Accumulator& prec) {
519 // A vector with a non-finite coefficient is orthogonal to nothing, a zero vector to everything.
520 if (!v.allFinite() || !w.allFinite()) return false;
521 // |<v, w>|^2 <= prec^2 |v|^2 |w|^2 between magnitudes that carry their own exponents.
522 const comparison_magnitude<Accumulator> absDot = unbounded_dot_magnitude(v, w);
523 comparison_magnitude<Accumulator> dot2 = absDot;
524 dot2.multiply(absDot);
525 comparison_magnitude<Accumulator> bound = unbounded_dot_magnitude(v, v);
526 bound.multiply(unbounded_dot_magnitude(w, w));
527 bound.multiply(prec);
528 bound.multiply(prec);
529 return dot2 <= bound;
530 }
531};
532
533} // end namespace internal
534
557template <typename Derived>
558template <typename OtherDerived>
559EIGEN_DEVICE_FUNC constexpr bool DenseBase<Derived>::isApprox(const DenseBase<OtherDerived>& other,
560 const RealScalar& prec) const {
561 return internal::isApprox_selector<Derived, OtherDerived>::run(derived(), other.derived(), prec);
562}
563
577template <typename Derived>
578EIGEN_DEVICE_FUNC constexpr bool DenseBase<Derived>::isMuchSmallerThan(const typename NumTraits<Scalar>::Real& other,
579 const RealScalar& prec) const {
580 return internal::isMuchSmallerThan_scalar_selector<Derived>::run(derived(), other, prec);
581}
582
593template <typename Derived>
594template <typename OtherDerived>
595EIGEN_DEVICE_FUNC constexpr bool DenseBase<Derived>::isMuchSmallerThan(const DenseBase<OtherDerived>& other,
596 const RealScalar& prec) const {
597 return internal::isMuchSmallerThan_object_selector<Derived, OtherDerived>::run(derived(), other.derived(), prec);
598}
599
606template <typename Derived>
607template <typename OtherDerived>
608bool MatrixBase<Derived>::isOrthogonal(const MatrixBase<OtherDerived>& other, const RealScalar& prec) const {
609 return internal::is_orthogonal_impl<Derived, OtherDerived>::run(derived(), other.derived(), prec);
610}
611
612} // end namespace Eigen
613
614#endif // EIGEN_APPROX_COMPARISONS_H
constexpr bool isApprox(const DenseBase< OtherDerived > &other, const RealScalar &prec=NumTraits< Scalar >::dummy_precision()) const
Definition ApproxComparisons.h:559
constexpr DenseBase()=default
constexpr CastXpr< NewType >::Type cast() const
Definition DenseBase.h:66
bool isOrthogonal(const MatrixBase< OtherDerived > &other, const RealScalar &prec=NumTraits< Scalar >::dummy_precision()) const
Definition ApproxComparisons.h:608
@ ColMajor
Definition Constants.h:319
@ RowMajor
Definition Constants.h:321