Swift Rational - Swift package for working with rational numbers

Community Showcase
, , ,
21

Sure, I can represent infinity or nan as division by zero, but that’s an additional condition I need to guard against for every operation. Also, throwing errors returns early, which is better than continuing a series of noop operations.

22

Int ops are doing that – I mean they are doing overflow checks on normal ops like +, -, *, etc and trapping if overflow happens – so that kind of checking overhead should be totally fine for Rationals.

Typically you optimise the "happy path", the "unhappy path" performance is not so important because it is considered to happen rarely.

1 Like
23

Where does Int do this? Isn’t NaN strictly a floating-point concept?

24

Tera means that the normal integer arithmetic operations like + all check for overflow (they trap, rather than return NaN, when it happens).

25

Can user-defined types participate in -Ounchecked?

26

You could probably abuse how precondition works:

precondition(try {
  if cond { throw err }
  return true
}())
27 
enum Optimization {
    case Onone, O, Ounchecked
    static var level: Self {
        var optimization: Self = .Ounchecked
        precondition({ optimization = .O; return true }())
        assert({ optimization = .Onone;  return true }())
        return optimization
    }
}
print(Optimization.level) // Onone, O, Uunchecked

Doesn't distinguish -O and -Osize though.

2 Likes
28

So, I thought about this, and I don’t think it’s the right path. What’s the quotient for infinity or NaN? What about floor and ceil? They are not of type Rational, so the obvious answer is to just trap. It’s not a safe API. When you add two values and they overflow, the expected behavior is to trap, at least for integers. I’d be very surprised if accessing quotient stopped my program entirely. I think either throwing an error or returning a Result-like value is a lot better. I like the latter approach because the returned error is typesafe, unlike throws.

29

That’s the behavior of Swift’s existing integer APIs. Why is it wrong for Rational?

30

Which properties trap in Int?

31

Overflowing operations trap.

32

Yes, I am aware. I already addressed this point. I said it’s fine to trap due to overflow, but I want all properties of Rational to be safe to access without errors.

33

Why do you think integer operations trap on overflow and floating point operations don't? If trapping was a superior behaviour why wouldn't floating point operations trap as well †?

I'd say the only possible explanation (other than "the tradition") is that floating point behaviour is superior, it's just impossible to follow it with integer arithmetic (sacrificing several valid integer value bit patterns to represent NaN / infinity, etc is not an option ††). This is not the case with Rationals which has a plenty of "unused" bit patterns to represent special values.

† They are not enabled by default but it is possible to enable floating point exceptions. 
func enableFloatingPointExceptions(_ options: Int = __fpcr_trap_invalid | __fpcr_trap_divbyzero | __fpcr_trap_overflow | __fpcr_trap_underflow | __fpcr_trap_inexact | __fpcr_trap_denormal | __fpcr_flush_to_zero) {
    var env = fenv_t()
    fegetenv(&env)
    env.__fpcr |= UInt64(options)
    fesetenv(&env)
    signal(SIGFPE, SIG_ERR);
}
†† How non-trapping (saturating) integer arithmetic could be implemented 
struct MyInteger: ExpressibleByIntegerLiteral, Hashable, Comparable {
    private static let overflowValue = Int.min
    var overflow: Bool { rawValue == Self.overflowValue }
    var rawValue: Int
    
    init(_ value: Int) {
        if value == Self.overflowValue { Self.reportOverflow() }
        rawValue = value
    }
    init(integerLiteral value: Int) {
        self.init(value)
    }
    init(_ result: (partialValue: Int, overflow: Bool)) {
        self.init(result.overflow ? Self.overflowValue : result.partialValue)
    }
    
    var integer: Int {
        if overflow {
            Self.reportOverflow()
            return 0
        }
        return rawValue
    }

    private static func reportOverflow() {
        #if LOG_ON_OVERFLOW
        print("overflow")
        #endif
        #if TRAP_ON_OVERFLOW
        fatalError("overflow")
        #endif
    }
    
    static func < (lhs: MyInteger, rhs: MyInteger) -> Bool {
        lhs.integer < rhs.integer
    }
    
    static func + (lhs: Self, rhs: Self) -> Self {
        Self(lhs.integer.addingReportingOverflow(rhs.integer))
    }
    .....
}
34

I'm not saying it's superior. I'm just saying that it needs extra care given that it's implemented with integer arithmetic, and the unused values would cause some properties in Rational to trap.

35

I use fractions to record measurements in a personal utility app I wrote and chucked something together, but I'd love to see a better more official way. Thank you for taking that on.

(FWIW: GitHub - carlynorama/Fractions: package for handling fractions mostly in measurement based applications, steal at will please if anything at all is useful, I really should chuck a license in there. Looks like the only thing there that you haven't already handled your own way is an initializer from a double, but that may not be a good call in a general purpose lib?)

One of the things I notice is that this library reduces on init. That would be lossy in my use case, a destruction of the original data collection.

I would low-key vote to have the numerator and denominator preserved as submitted with a function/variable that returns a reduced value. (In my measurement storage backing library I preserve the whole number as well if entered, but I understand that in a general purpose rational number library preserving that would be a harder sell)

FWIW: There is a GCD implementation in IntegerUtilites that you could pull in instead of rolling your own?

See also the approach arithmetic, not sure if useful.

1 Like
36

So, the reason why all values are reduced is because this is almost a direct port of Python's "fractions" module. It also makes the implementation easier and fast because you don't need to check if the values are reduced before every operation. You can store an internal flag, but similar to using a sign bit, you lose memory compactness in return.

EDIT:
The GCD implementation I'm using is exactly the one you linked to. It's just not for available for public use, so I copied it.

1 Like
37

Makes sense. Matching other libraries and behaving as expected is a good policy. For my measurement capture purposes the denominator is a significant figures indicator. An original value of 5 16/32 implies better fidelity than 5 1/2, but that measurement specific info can, and possibly should, be stored in a data type that wraps a Rational.

Oh, really still? I feel like I just saw... Well anyway... I'm looking forward to that set of tools too! (EDIT - Note... it is REALLY hard to search the Swifty-verse for GCD meaning greatest common denominator to try to find the reference you were thinking of :joy: (Looking a you Grand Central Dispatch, looking at you)) This was the place, talking about the lack of release not the release: Advent of Code 2023 - #44 by jim

1 Like
38

Suppose I have a rational with a very large numerator and denominator and one of those overflows during a computation. I don’t think it makes sense to round to zero or infinity in that case.

39

Yeah, if I'm working with a rational type, I expect to get an explicit error on overflow one way or another.

2 Likes
40

Why not, floating point is doing this, do you think rational can't? It would be one of valid approaches, which are:

  1. log to console
  2. return an "arbitrary" result (like 0)
  3. always "wrap"
  4. saturate to NaN/infinity/etc
  5. trap
  6. call user provided error handler
  7. throw
  8. return Result<Rational, Error>
  9. return Optional<Rational>
  10. return (partialResult: Rational, overflow: Bool)

Some options like 1 could be combined with others. When working with integer arithmetic we could choose between 3, 5 and 10, while when working with floating point arithmetic between 4 and 4+5.