# Swift Rational - Swift package for working with rational numbers

Swift Rational provides the `RationalModule` module for working with rational numbers in Swift.

`RationalModule` exports the `Rational` struct. It conforms to standard Swift protocols like `AdditiveArithmetic`, `Numeric`, `Hashable`, `Comparable`, and more.

You can create a `Rational` value using the fraction initializer.

``````let half = Rational(2, 4)
print(x.numerator)		// 1
print(x.denominator).	// 2
``````

You can also use the integer initializer.

``````let one = Rational(1)
``````

Or simply an integer literal.

``````let two: Rational<Int> = 2
``````

`Rational` supports the standard arithmetic and comparison operators.

``````Rational(1, 2) + Rational(1, 4)		// Rational(3, 4)
Rational(1)    - Rational(1, 2)		// Rational(1, 2)
Rational(2)    * Rational(3, 4)		// Rational(3, 2)
Rational(1)    / Rational(1, 2)		// Rational(2, 1)
Rational(1, 2) < Rational(3, 4)		// true
``````
10 Likes

Nice!

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.

6 Likes

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).

2 Likes

I really like this package

But I am wondering: wouldn’t this be fine addition to Swift Numerics?

1 Like

Hey! An unfortunate consequence of relying on `FixedWidthInteger`s 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?

Hey thanks! I don’t mind contributing to `swift-numerics` directly, but I don’t think the contribution would be accepted due to the lack of tests.

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.

6 Likes

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).

1 Like

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.
2 Likes

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.

Generally you want to make `gcd()` a requirement as well, since it can be implemented in various different ways for each domain.

2 Likes

Excellent point. Perhaps with the default implementation in a protocol extension for those cases it's good 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?

1 Like

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!

1 Like

I created a PR with some tests. Please have a look. If this is what you need, I can make some more!

2 Likes

I just merged your tests. Thanks a lot! I'll continue working on this library the next couple of days. I want to add "safe" arithmetic operators.

I'm thinking of (ab)using the "&" operators for this purpose.

``````Rational.max &+ 1	// throws an error
``````

The alternative is to implement them using methods, which is not that great for chaining multiple operators together.

``````Rational(1, 2).safeAdd(Rational(3, 2).safeMultiply(3))
Rational(1, 2) &+ Rational(3, 2) &* 3
``````

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.

1 Like

I quite like this, but why not use a seperate `sign bit`, and `unsigned` `numerator` and `denominator` to extend their ranges?

1 Like

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).