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.
149 lines
5.6 KiB
Swift
149 lines
5.6 KiB
Swift
//===--- AugmentedArithmetic.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
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
public enum Augmented { }
|
|
|
|
extension Augmented {
|
|
/// The product `a * b` represented as an implicit sum `head + tail`.
|
|
///
|
|
/// `head` is the correctly rounded value of `a*b`. If no overflow or
|
|
/// underflow occurs, `tail` represents the rounding error incurred in
|
|
/// computing `head`, such that the exact product is the sum of `head`
|
|
/// and `tail` computed without rounding.
|
|
///
|
|
/// This operation is sometimes called "twoProd" or "twoProduct".
|
|
///
|
|
/// Edge Cases:
|
|
///
|
|
/// - `head` is always the IEEE 754 product `a * b`.
|
|
/// - If `head` is not finite, `tail` is unspecified and should not be
|
|
/// interpreted as having any meaning (it may be `NaN` or `infinity`).
|
|
/// - When `head` is close to the underflow boundary, the rounding error
|
|
/// may not be representable due to underflow, and `tail` will be rounded.
|
|
/// If `head` is very small, `tail` may even be zero, even though the
|
|
/// product is not exact.
|
|
/// - If `head` is zero, `tail` is also a zero with unspecified sign.
|
|
///
|
|
/// Postconditions:
|
|
///
|
|
/// - If `head` is normal, then `abs(tail) < head.ulp`.
|
|
/// Assuming IEEE 754 default rounding, `abs(tail) <= head.ulp/2`.
|
|
/// - If both `head` and `tail` are normal, then `a * b` is exactly
|
|
/// equal to `head + tail` when computed as real numbers.
|
|
@_transparent
|
|
public static func product<T:FloatingPoint>(
|
|
_ a: T, _ b: T
|
|
) -> (head: T, tail: T) {
|
|
let head = a*b
|
|
// TODO: consider providing an FMA-less implementation for use when
|
|
// targeting platforms without hardware FMA support. This works everywhere,
|
|
// falling back on the C math.h fma funcions, but may be slow on older x86.
|
|
let tail = (-head).addingProduct(a, b)
|
|
return (head, tail)
|
|
}
|
|
|
|
/// The sum `a + b` represented as an implicit sum `head + tail`.
|
|
///
|
|
/// - Parameters:
|
|
/// - a: The summand with larger magnitude.
|
|
/// - b: The summand with smaller magnitude.
|
|
///
|
|
/// `head` is the correctly rounded value of `a + b`. `tail` is the
|
|
/// error from that computation rounded to the closest representable
|
|
/// value.
|
|
///
|
|
/// > Note:
|
|
/// > `tail` is guaranteed to be the best approximation to the error of
|
|
/// the sum only if `large.magnitude` >= `small.magnitude`. If this is
|
|
/// not the case, then `head` is the correctly rounded sum, but `tail`
|
|
/// is not guaranteed to be the exact error. If you do not know a priori
|
|
/// how the magnitudes of `a` and `b` compare, you likely want to use
|
|
/// ``sum(_:_:)`` instead.
|
|
///
|
|
/// Unlike ``product(_:_:)``, the rounding error of `sum` never underflows.
|
|
///
|
|
/// This operation is sometimes called ["fastTwoSum"].
|
|
///
|
|
/// > Note:
|
|
/// > Classical fastTwoSum does not work when `radix` is 10. This function
|
|
/// will fall back on another algorithm for decimal floating-point types
|
|
/// to ensure correct results.
|
|
///
|
|
/// Edge Cases:
|
|
///
|
|
/// - `head` is always the IEEE 754 sum `a + b`.
|
|
/// - If `head` is not finite, `tail` is unspecified and should not be
|
|
/// interpreted as having any meaning (it may be `NaN` or `infinity`).
|
|
///
|
|
/// Postconditions:
|
|
///
|
|
/// - If `head` is normal, then `abs(tail) < head.ulp`.
|
|
/// Assuming IEEE 754 default rounding, `abs(tail) <= head.ulp/2`.
|
|
///
|
|
/// ["fastTwoSum"]: https://en.wikipedia.org/wiki/2Sum
|
|
@_transparent
|
|
public static func sum<T: FloatingPoint>(
|
|
large a: T, small b: T
|
|
) -> (head: T, tail: T) {
|
|
// Fall back on 2Sum if radix != 2. Future implementations might use an
|
|
// cheaper algorithm specialized for decimal FP, but must deliver a
|
|
// correct result if the preconditions are satisfied.
|
|
guard T.radix == 2 else { return sum(a, b) }
|
|
// Fast2Sum:
|
|
let head = a + b
|
|
let tail = a - head + b
|
|
return (head, tail)
|
|
}
|
|
|
|
/// The sum `a + b` represented as an implicit sum `head + tail`.
|
|
///
|
|
/// `head` is the correctly rounded value of `a + b`. `tail` is the
|
|
/// error from that computation rounded to the closest representable
|
|
/// value.
|
|
///
|
|
/// The magnitude of the summands does not change the result of this
|
|
/// operation. If you know statically that `a.magnitude >= b.magnitude`,
|
|
/// you may want to consider using ``sum(large:small:)`` to get the same
|
|
/// result somewhat more efficiently. If you do not have such a static
|
|
/// bound, you usually want to use this function instead.
|
|
///
|
|
/// Unlike ``product(_:_:)``, the rounding error of `sum` never underflows.
|
|
///
|
|
/// This operation is sometimes called ["twoSum"].
|
|
///
|
|
/// - Parameters:
|
|
/// - a: One of the summands
|
|
/// - b: The other summand
|
|
///
|
|
/// Edge Cases:
|
|
///
|
|
/// - `head` is always the IEEE 754 sum `a + b`.
|
|
/// - If `head` is not finite, `tail` is unspecified and should not be
|
|
/// interpreted as having any meaning (it may be `NaN` or `infinity`).
|
|
///
|
|
/// Postconditions:
|
|
///
|
|
/// - If `head` is normal, then `abs(tail) < head.ulp`.
|
|
/// Assuming IEEE 754 default rounding, `abs(tail) <= head.ulp/2`.
|
|
///
|
|
/// ["twoSum"]: https://en.wikipedia.org/wiki/2Sum
|
|
@_transparent
|
|
public static func sum<T: FloatingPoint>(
|
|
_ a: T, _ b: T
|
|
) -> (head: T, tail: T) {
|
|
let head = a + b
|
|
let x = head - b
|
|
let y = head - x
|
|
let tail = (a - x) + (b - y)
|
|
return (head, tail)
|
|
}
|
|
}
|