How to: detect overflow for `dividingFullWidth` without trapping

Using Swift
1

There have been a few threads over the years about how best to detect overflow cases in dividingFullWidth without trapping (especially for signed integers, as it's quite straightforward for unsigned).

I want to lay out a correct method for performing these operations for people to be able to reference if they need it. It's not obvious to me that these belong in the standard library (or even in Numerics), but I can at least make them available here.

Note that, unlike the [adding, subtracting, multiplied]ReportingOverflow methods, these do not return a wrapped "partial result" and an overflow flag; they simply return nil when the result overflows. This is because computing a wrapped partial result is actually quite a bit of extra work in general, and there are few--if any--numerical algorithms that would benefit from having it available.

extension FixedWidthInteger where Self: UnsignedInteger {
  /// Returns an optional tuple containing the quotient and remainder
  /// obtained by dividing the given value by this value if the quotient
  /// is representable, and nil otherwise.
  ///
  /// If the result is a non-nil value, the result is identical to
  /// `self.dividingFullWidth(dividend)`. If the result is `nil`,
  /// then the same call to `dividingFullWidth` would have generated
  /// a runtime trap, because either the divisor is zero or the quotient
  /// is not representable.
  func dividingFullWidthIfRepresentable(
    _ dividend: (high: Self, low: Magnitude)
  ) -> (quotient: Self, remainder: Self)? {
    guard self != 0 else { return nil }
    guard self > dividend.high else { return nil }
    return dividingFullWidth(dividend)
  }
}

extension FixedWidthInteger where Self: SignedInteger {
  /// Returns an optional tuple containing the quotient and remainder
  /// obtained by dividing the given value by this value if the quotient
  /// is representable, and nil otherwise.
  ///
  /// If the result is a non-nil value, the result is identical to
  /// `self.dividingFullWidth(dividend)`. If the result is `nil`,
  /// then the same call to `dividingFullWidth` would have generated
  /// a runtime trap, because either the divisor is zero or the quotient
  /// is not representable.
  func dividingFullWidthIfRepresentable(
    _ dividend: (high: Self, low: Magnitude)
  ) -> (quotient: Self, remainder: Self)? {
    guard self != 0 else { return nil }
    // Get magnitude of dividend and divisor and do an unsigned divide.
    let unsignedDivisor = self.magnitude
    var unsignedLow = dividend.low
    var unsignedHigh = Magnitude(truncatingIfNeeded: dividend.high)
    if dividend.high < 0 {
      let carry: Bool
      (unsignedLow, carry) = (~unsignedLow).addingReportingOverflow(1)
      unsignedHigh = ~unsignedHigh &+ (carry ? 1 : 0)
    }
    guard unsignedHigh < unsignedDivisor else { return nil }
    // Unsigned division is now safe:
    let (unsignedQ, unsignedR) = unsignedDivisor.dividingFullWidth(
      (high: unsignedHigh, low: unsignedLow)
    )
    // Apply the correct sign to the quotient, and check that the signed
    // quotient is actually representable as Self:
    let quotient: Self
    if self ^ dividend.high < .zero {
      guard unsignedQ <= Self.min.magnitude else { return nil }
      quotient = Self(truncatingIfNeeded: 0 &- unsignedQ)
    } else {
      guard unsignedQ <= Self.max.magnitude else { return nil }
      quotient = Self(unsignedQ)
    }
    // Apply the correct sign to the remainder; we do not need to check
    // for overflow here because the division guarantees that
    // unsignedR < self.magnitude.
    var remainder = Self(unsignedR)
    if dividend.high < .zero { remainder = 0 &- remainder }
    return (quotient, remainder)
  }
}
12 Likes