mirror of
https://github.com/apple/swift-numerics
synced 2026-11-22 04:30:45 +00:00
This commit _also_ relaxes the constraint on Augmented algorithms from Real to FloatingPoint. It's worth calling out that fastTwoSum does not work with decimal floating-point types, so the unordered `Augemented.sum(_:_:)` now has a radix check and calls into the ordered twoSum function instead for Decimal. This makes more sense that a `BinaryFloatingPoint` constraint, as otherwise generic code written against Real or FloatingPoint would have to do the check at every call site.
248 lines
9.4 KiB
Swift
248 lines
9.4 KiB
Swift
//===--- ApproximateEquality.swift ----------------------------*- swift -*-===//
|
|
//
|
|
// This source file is part of the Swift Numerics open source project
|
|
//
|
|
// Copyright (c) 2020-2025 Apple Inc. and the Swift Numerics project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
extension Numeric where Magnitude: FloatingPoint {
|
|
/// Test if `self` and `other` are approximately equal.
|
|
///
|
|
/// `true` if `self` and `other` are equal, or if they are finite and
|
|
/// ```
|
|
/// norm(self - other) <= relativeTolerance * scale
|
|
/// ```
|
|
/// where `scale` is
|
|
/// ```
|
|
/// max(norm(self), norm(other), .leastNormalMagnitude)
|
|
/// ```
|
|
///
|
|
/// The default value of `relativeTolerance` is `.ulpOfOne.squareRoot()`,
|
|
/// which corresponds to expecting "about half the digits" in the computed
|
|
/// results to be good. This is the usual guidance in numerical analysis,
|
|
/// if you don't know anything about the computation being performed, but
|
|
/// is not suitable for all use cases.
|
|
///
|
|
/// Mathematical Properties:
|
|
///
|
|
/// - `isApproximatelyEqual(to:relativeTolerance:norm:)` is _reflexive_ for
|
|
/// non-exceptional values (such as NaN).
|
|
///
|
|
/// - `isApproximatelyEqual(to:relativeTolerance:norm:)` is _symmetric_.
|
|
///
|
|
/// - `isApproximatelyEqual(to:relativeTolerance:norm:)` is __not__
|
|
/// _transitive_. Because of this, approximately equality is __not an
|
|
/// equivalence relation__, even when restricted to non-exceptional values.
|
|
///
|
|
/// This means that you must not use approximate equality to implement
|
|
/// a conformance to Equatable, as it will violate the invariants of
|
|
/// code written against that protocol.
|
|
///
|
|
/// - For any point `a`, the set of values that compare approximately equal
|
|
/// to `a` is _convex_. (Under the assumption that the `.magnitude`
|
|
/// property implements a valid norm.)
|
|
///
|
|
/// - `isApproximatelyEqual(to:relativeTolerance:norm:)` is _scale invariant_,
|
|
/// so long as no underflow or overflow has occurred, and no exceptional
|
|
/// value is produced by the scaling.
|
|
///
|
|
/// See also `isApproximatelyEqual(to:absoluteTolerance:[relativeTolerance:norm:])`.
|
|
///
|
|
/// - Parameters:
|
|
///
|
|
/// - other: The value to which `self` is compared.
|
|
///
|
|
/// - relativeTolerance: The tolerance to use for the comparison.
|
|
/// Defaults to `.ulpOfOne.squareRoot()`.
|
|
///
|
|
/// This value should be non-negative and less than or equal to 1.
|
|
/// This constraint on is only checked in debug builds, because a
|
|
/// mathematically well-defined result exists for any tolerance,
|
|
/// even one out of range.
|
|
///
|
|
/// - norm: The [norm] to use for the comparison.
|
|
/// Defaults to `\.magnitude`.
|
|
///
|
|
/// [norm]: https://en.wikipedia.org/wiki/Norm_(mathematics)
|
|
@inlinable @inline(__always)
|
|
public func isApproximatelyEqual(
|
|
to other: Self,
|
|
relativeTolerance: Magnitude = Magnitude.ulpOfOne.squareRoot(),
|
|
norm: (Self) -> Magnitude = \.magnitude
|
|
) -> Bool {
|
|
return isApproximatelyEqual(
|
|
to: other,
|
|
absoluteTolerance: relativeTolerance * Magnitude.leastNormalMagnitude,
|
|
relativeTolerance: relativeTolerance,
|
|
norm: norm
|
|
)
|
|
}
|
|
|
|
/// Test if `self` and `other` are approximately equal with specified tolerances.
|
|
///
|
|
/// `true` if `self` and `other` are equal, or if they are finite and either
|
|
/// ```
|
|
/// (self - other).magnitude <= absoluteTolerance
|
|
/// ```
|
|
/// or
|
|
/// ```
|
|
/// (self - other).magnitude <= relativeTolerance * scale
|
|
/// ```
|
|
/// where `scale` is `max(self.magnitude, other.magnitude)`.
|
|
///
|
|
/// Mathematical Properties:
|
|
///
|
|
/// - `isApproximatelyEqual(to:absoluteTolerance:relativeTolerance:)`
|
|
/// is _reflexive_ for non-exceptional values (such as NaN).
|
|
///
|
|
/// - `isApproximatelyEqual(to:absoluteTolerance:relativeTolerance:)`
|
|
/// is _symmetric_.
|
|
///
|
|
/// - `isApproximatelyEqual(to:relativeTolerance:norm:)` is __not__
|
|
/// _transitive_. Because of this, approximately equality is __not an
|
|
/// equivalence relation__, even when restricted to non-exceptional values.
|
|
///
|
|
/// This means that you must not use approximate equality to implement
|
|
/// a conformance to Equatable, as it will violate the invariants of
|
|
/// code written against that protocol.
|
|
///
|
|
/// - For any point `a`, the set of values that compare approximately equal
|
|
/// to `a` is _convex_. (Under the assumption that `norm` implements a
|
|
/// valid norm, which cannot be checked by this function.)
|
|
///
|
|
/// See also `isApproximatelyEqual(to:[relativeTolerance:])`.
|
|
///
|
|
/// - Parameters:
|
|
///
|
|
/// - other: The value to which `self` is compared.
|
|
///
|
|
/// - absoluteTolerance: The absolute tolerance to use in the comparison.
|
|
///
|
|
/// This value should be non-negative and finite.
|
|
/// This constraint on is only checked in debug builds, because a
|
|
/// mathematically well-defined result exists for any tolerance,
|
|
/// even one out of range.
|
|
///
|
|
/// - relativeTolerance: The relative tolerance to use in the comparison.
|
|
/// Defaults to zero.
|
|
///
|
|
/// This value should be non-negative and less than or equal to 1.
|
|
/// This constraint on is only checked in debug builds, because a
|
|
/// mathematically well-defined result exists for any tolerance,
|
|
/// even one out of range.
|
|
@inlinable @inline(__always)
|
|
public func isApproximatelyEqual(
|
|
to other: Self,
|
|
absoluteTolerance: Magnitude,
|
|
relativeTolerance: Magnitude = 0
|
|
) -> Bool {
|
|
self.isApproximatelyEqual(
|
|
to: other,
|
|
absoluteTolerance: absoluteTolerance,
|
|
relativeTolerance: relativeTolerance,
|
|
norm: \.magnitude
|
|
)
|
|
}
|
|
}
|
|
|
|
extension AdditiveArithmetic {
|
|
/// Test if `self` and `other` are approximately equal with specified
|
|
/// tolerances and norm.
|
|
///
|
|
/// `true` if `self` and `other` are equal, or if they are finite and either
|
|
/// ```
|
|
/// norm(self - other) <= absoluteTolerance
|
|
/// ```
|
|
/// or
|
|
/// ```
|
|
/// norm(self - other) <= relativeTolerance * scale
|
|
/// ```
|
|
/// where `scale` is `max(norm(self), norm(other))`.
|
|
///
|
|
/// Mathematical Properties:
|
|
///
|
|
/// - `isApproximatelyEqual(to:absoluteTolerance:relativeTolerance:norm:)`
|
|
/// is _reflexive_ for non-exceptional values (such as NaN).
|
|
///
|
|
/// - `isApproximatelyEqual(to:absoluteTolerance:relativeTolerance:norm:)`
|
|
/// is _symmetric_.
|
|
///
|
|
/// - `isApproximatelyEqual(to:absoluteTolerance:relativeTolerance:norm:)`
|
|
/// is __not__ _transitive_. Because of this, approximately equality is
|
|
/// __not an equivalence relation__, even when restricted to
|
|
/// non-exceptional values.
|
|
///
|
|
/// This means that you must not use approximate equality to implement
|
|
/// a conformance to Equatable, as it will violate the invariants of
|
|
/// code written against that protocol.
|
|
///
|
|
/// - For any point `a`, the set of values that compare approximately equal
|
|
/// to `a` is _convex_ (under the assumption that `norm` implements a
|
|
/// valid norm, which cannot be checked by this function or a protocol).
|
|
///
|
|
/// See also `isApproximatelyEqual(to:[relativeTolerance:norm:])` and
|
|
/// `isApproximatelyEqual(to:absoluteTolerance:[relativeTolerance:])`.
|
|
///
|
|
/// - Parameters:
|
|
///
|
|
/// - other: The value to which `self` is compared.
|
|
///
|
|
/// - absoluteTolerance: The absolute tolerance to use in the comparison.
|
|
///
|
|
/// This value should be non-negative and finite.
|
|
/// This constraint on is only checked in debug builds, because a
|
|
/// mathematically well-defined result exists for any tolerance, even
|
|
/// one out of range.
|
|
///
|
|
/// - relativeTolerance: The relative tolerance to use in the comparison.
|
|
/// Defaults to zero.
|
|
///
|
|
/// This value should be non-negative and less than or equal to 1.
|
|
/// This constraint on is only checked in debug builds, because a
|
|
/// mathematically well-defined result exists for any tolerance,
|
|
/// even one out of range.
|
|
///
|
|
/// - norm: The norm to use for the comparison.
|
|
/// Defaults to `\.magnitude`.
|
|
///
|
|
/// For example, if we wanted to test if a complex value was inside a
|
|
/// circle of radius 0.001 centered at (1 + 0i), we could use:
|
|
/// ```
|
|
/// z.isApproximatelyEqual(
|
|
/// to: 1,
|
|
/// absoluteTolerance: 0.001,
|
|
/// norm: \.length
|
|
/// )
|
|
/// ```
|
|
/// (if we used the default norm, `\.magnitude`, we would be testing if
|
|
/// `z` were inside a square region instead.)
|
|
@inlinable
|
|
public func isApproximatelyEqual<Magnitude>(
|
|
to other: Self,
|
|
absoluteTolerance: Magnitude,
|
|
relativeTolerance: Magnitude = 0,
|
|
norm: (Self) -> Magnitude
|
|
) -> Bool
|
|
where Magnitude: FloatingPoint {
|
|
assert(
|
|
absoluteTolerance >= 0 && absoluteTolerance.isFinite,
|
|
"absoluteTolerance should be non-negative and finite, " +
|
|
"but is \(absoluteTolerance)."
|
|
)
|
|
assert(
|
|
relativeTolerance >= 0 && relativeTolerance <= 1,
|
|
"relativeTolerance should be non-negative and <= 1, " +
|
|
"but is \(relativeTolerance)."
|
|
)
|
|
if self == other { return true }
|
|
let delta = norm(self - other)
|
|
let scale = max(norm(self), norm(other))
|
|
let bound = max(absoluteTolerance, scale*relativeTolerance)
|
|
return delta.isFinite && delta <= bound
|
|
}
|
|
}
|