[swift-users] A sample Rational number type

[Dave Abrahams]

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

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

Have you thought about what this would look like after we land
https://github.com/apple/swift/pull/3796 (see
https://github.com/apple/swift-evolution/blob/master/proposals/0104-improved-integers.md)
?

You can also find a working prototype of that code at
https://github.com/apple/swift/blob/b7622b41756e33bdf3f3415320ffec52aec73281/test/Prototypes/Integers.swift.gyb
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?

There's a BigInt implementation based on these protocols here:
https://github.com/natecook1000/swift/commit/45c52a75dcc15024649a5e093a5da4ee031595c2

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:
https://en.wikipedia.org/wiki/Binary_GCD_algorithm#cite_note-11

I wonder how that should be dispatched...

-- 
-Dave