For anybody who is interested: This gist <https://gist.github.com/hooman/6e08c48e1e06ee19e06e5b09f664f9be> contains a Rational number implementation for Swift 3.0. It is a single file that you can paste in a playground and take a look, or remove the last few lines and drop the file into your own module. The recommended way to create a rational number is specifying Rational type as in:

let r: Rational = 18/64
// or
let x = 5 + 2/3 as Rational

or use tolerance operator `±` to convert from floating point:

let r2 = 2.109±0.0005 // 2⁷⁄₆₄

Rational type conforms to AbsoluteValuable (hence Equatable, Comparable, ExpressibleByIntegerLiteral, SignedNumber), Strideable, and CustomStringConvertible.

It always uses fully-reduced representation for simplicity and clarity of comparisons and uses LCM (lowest common multiple) for addition & subtraction to reduce the chance of overflow in the middle of computations. The disadvantage of these design choices are: It is not guaranteed to keep the nominator and denominator as specified during construction, and GCD / LCM computations reduce its performance.

The performance trade-off is not huge and is usually acceptable for typical rational number use cases. Preserving denominator can be addressed with a number formatter for rational numbers that I will add later. GCD is computed with Stein's algorithm (binary GCD algorithm).

For anybody who is interested: This gist
<https://gist.github.com/hooman/6e08c48e1e06ee19e06e5b09f664f9be>
contains a Rational number implementation for Swift 3.0. It is a
single file that you can paste in a playground and take a look, or
remove the last few lines and drop the file into your own module. The
recommended way to create a rational number is specifying Rational
type as in:

let r: Rational = 18/64
// or
let x = 5 + 2/3 as Rational

or use tolerance operator `±` to convert from floating point:

let r2 = 2.109±0.0005 // 2⁷⁄₆₄

Presumably you mean:

let r2 = r±0.0005 // turn a Rational into a Double with no more than
// .0005 rounding error

? That is supercute!

Rational type conforms to AbsoluteValuable (hence Equatable,
Comparable, ExpressibleByIntegerLiteral, SignedNumber), Strideable,
and CustomStringConvertible.

You can also find a working prototype of that code at

It would be great to know that the protocols we've designed actually
work out for Rational numbers. With these protocols, can you make your
Rational generic on the underlying integer type?

It would be really cool to see it work with a generic version of your
Rational type.

It always uses fully-reduced representation for simplicity and clarity
of comparisons and uses LCM (lowest common multiple) for addition &
subtraction to reduce the chance of overflow in the middle of
computations. The disadvantage of these design choices are: It is not
guaranteed to keep the nominator and denominator as specified during
construction, and GCD / LCM computations reduce its performance.

The performance trade-off is not huge and is usually acceptable for
typical rational number use cases. Preserving denominator can be
addressed with a number formatter for rational numbers that I will add
later. GCD is computed with Stein's algorithm (binary GCD algorithm).

It's interesting to see that one wants a different algorithm for GCD
when using BigInts:

I wonder how that should be dispatched...

···

on Fri Sep 30 2016, Hooman Mehr <swift-users-AT-swift.org> wrote:

let r2 = r±0.0005 // turn a Rational into a Double with no more than
// .0005 rounding error

? That is supercute!

It is actually the other way around: It returns a rational given a double so that the maximum difference of the created rational with the input double is the specified tolerance.

Moreover, there is something I ran into after posting: On today’s CPU architectures with fast integer divide, simple binary CGD is slower than basic Euler’s algorithm using remainders. Binary GCD needs the equivalent of __builtin_ctz to run faster. It would be nice if compiler could detect the shift loops and replace the whole loop with x86 BSFL instruction.

I need to put some thought on whether there is an efficient means of switching the algorithm based on the actual size (or nature) of the given Int type, otherwise we may have to specialize, which is not good from a generics standpoint.

···

On Oct 2, 2016, at 5:23 PM, Dave Abrahams via swift-users <swift-users@swift.org> wrote:

let r2 = r±0.0005 // turn a Rational into a Double with no more than
// .0005 rounding error

? That is supercute!

It is actually the other way around: It returns a rational given a
double so that the maximum difference of the created rational with the
input double is the specified tolerance.

It would be great to know that the protocols we've designed actually
work out for Rational numbers. With these protocols, can you make your
Rational generic on the underlying integer type?

Moreover, there is something I ran into after posting: On today’s CPU
architectures with fast integer divide, simple binary CGD is slower
than basic Euler’s algorithm using remainders. Binary GCD needs the
equivalent of __builtin_ctz to run faster.

The new integer protocols expose that as a "leadingZeros" property.

It would be nice if compiler could detect the shift loops and replace
the whole loop with x86 BSFL instruction.

Talk to the llvm people :-). You'll want to use masking shifts under
the new integer protocols.

I need to put some thought on whether there is an efficient means of
switching the algorithm based on the actual size (or nature) of the
given Int type, otherwise we may have to specialize, which is not good
from a generics standpoint.

It depends exactly what you mean by that term :-)

···

on Sun Oct 02 2016, Hooman Mehr <swift-users-AT-swift.org> wrote:

On Oct 2, 2016, at 5:23 PM, Dave Abrahams via swift-users <swift-users@swift.org> wrote:

SR-2868 <Issues · apple/swift-issues · GitHub If the value of the floating point type is a power of two, its `significandWidth` property returns a nonsense value, because the behavior or Builtin.int_cttz_IntNN (used in countTrailingZeros property) is undefined for zero.

The test suite should have included such special cases and caught this one.

···

On Oct 3, 2016, at 9:08 AM, Dave Abrahams via swift-users <swift-users@swift.org> wrote: