Do you have plans to make the implementation robust against spurious overflow?
For example:
let a = Rational<Int8>(16, 35)
let b = Rational<Int8>(39, 85)
let c = a + b // should be 109/119
If I’m reading the code for “+” properly, the current implementation in RationalModule will trap when computing c because some of the intermediate results overflow Int8. Specifically, the line let t = n1 * (d2 / g) + n2 * s in Rational+AdditiveArithmetic.swift will trap.
I described this issue, and briefly outlined a solution using full-width multiplication and division, in this thread last year.
The Lisp fan in me wants to point out that you really ought to use Rational<BigInt> instead. And while you're at it, we can further extend the Lisp "number tower" by introducing a Polynomial<T> type. This will compose with Rational of course, so you'll be able to do arithmetic on Rational<Polynomial<BigInt>> (or even Rational<Polynomial<Rational<BigInt>>>; exercise for the reader to show that these two are isomorphic).
Hey! An unfortunate consequence of relying on FixedWidthIntegers is very fast overflow. I don’t think further optimization is worth it and it might just be better to have a separate BigRational type. Is there a good BigInt implementation I can rely on?
Nevin's point is that you can avoid intermediate overflow, where the final result is representable but subcomponents of the computation are not. This is pretty valuable to do, especially for fixed-width types.
You could make your implementation more generic by requiring only what's essential to your implementation.
Something like this (very draft implementation, should be cleaned)
public protocol RationalRequirements: ExpressibleByIntegerLiteral, Hashable, Comparable, AdditiveArithmetic {
mutating func negate()
func abs() -> Self
var isNegative: Bool { get }
var isPositive: Bool { get }
var isZero: Bool { get }
var isOne: Bool { get }
var geOne: Bool { get }
func decreased() -> Self
func increased() -> Self
static var min: Self { get }
static var max: Self { get }
static prefix func - (_ v: Self) -> Self
static func / (lhs: Self, rhs: Self) -> Self
static func * (lhs: Self, rhs: Self) -> Self
static func % (lhs: Self, rhs: Self) -> Self
func dividingBy(_ other: Self) -> (quotient: Self, remainder: Self)
func quotientAndRemainder(dividingBy: Self) -> (quotient: Self, remainder: Self)
func multipliedReportingOverflow(by: Self) -> (result: Self, overflow: Bool)
func multipliedFullWidth(by: Self) -> Self
var magnitude: Int { get }
func signum() -> Self
init(_ v: Int)
init?(_ v: String)
init?(_ v: Substring)
init?<R: BinaryInteger>(exactly: R)
}
Then any type conforming to those requirements (be it one of Swift's fixed integer types or StaticBigNum or VariableBigNum or etc) would be compatible with your implementation so long as they implement the required minimum (either out of the box or with minimal additions).
Another way to cut it, which would help mitigate the intermediate overflow problem, would be to have the RationalRequirements protocol only require conversions to and from some large-enough computation type like Int64 or Bignum*. Then the rational implementation can do all its internal computation using that common type and only needs to overflow-check and truncate down the final result.
though as Slava somewhat alluded to, the tendency for variable-denominator rational computations to blow up exponentially in the number of operations tends to make non-arbitrary-precision rationals difficult to fit inside even for relatively large component types, so having only arbitrary-precision rational as a nongeneric type is also a reasonable direction.
How about this?
1- Add safe arithmetic operators that throw on overflow.
2- Add BigRational in a separate module in the same package for cases when Int64 is not enough.
I just checked the repo, there is about a 50% test coverage. So I guess it should be possible to provide some more tests. Are you planning to add more tests? Or would you like me to have a stab at creating some tests?
I’ve been thinking about adding some samples with the results of addition, subtraction, multiplication, and division using Python. If you’re willing to add some tests, though, I’d highly appreciate it!
My recommendation would be to use the (throwing) methods to implement safe operations.
Because the &+ set of operators are used by Swift for 'do stuff with overflow' which is very different from the intended use here.
Note: overflowing operators might have their (separate) uses.
A couple of reasons.
1- It greatly simplifies the code. No need for branching on the sign bit.
2- It’s more performant because of 1.
3- It can be represented compactly in memory as 2 * sizeof(T), whereas with a sign bit, it gets padded I believe.
Rational<UInt32> would take up 2 * 32 bits + 1 sign bit. In an array, this is padded to 128 bits.
As far as overflow, etc is concerned you may do it similarly to floating point ops: saturate to a special value (like inf or nan) and stick to it throughout subsequent operations, maybe along with plotting the fact of overflow / underflow / etc to the console (and optionally trapping depending on a compiler/debugging option). For example these could be special value "markers":
// Rational numerator and denominator:
1 / 0 – positive infinity
-1 / 0 – negative infinity
0 / 0 – nan
0 / 1 – positive zero
0 / -1 – negative zero
N / 0, N ∉ (-1, 0, 1) – reserved
0 / N, N ∉ (-1, 0, 1) – reserved
Worth to consider what would (and should) happen on mid-expression overflow/underflow even when the final result is ok like in the below example (Rational<UInt8> ahead):
200/255 + 100/255 - 60/255
Throwing ops are inconvenient for the same reason they are inconvenient for normal Int or float ops: too much noise ("try", etc) on the use sites).
