Thursday, 29 August 2013

Implementing rationals in F#

.NET 4 introduced the System.Numerics namespace that includes the BigInteger and Complex number types. The BigInteger type can be used to construct a Rational type that can represent arbitrary-precision rational numbers. A simple implementation that just exposes construction with cancellation of the greatest common divisor (GCD) from numerator and denominator as well as the four basic arithmetic operations is remarkably elegant when written in F#:

type Rational(p: BigInteger, q: BigInteger) =
  let rec gcd a (b: BigInteger) =
    if b.IsZero then a else
      gcd b (a % b)

  let fixSign(p: BigInteger, q: BigInteger) =
    if q.Sign > 0 then p, q else -p, -q

  let p, q =
    if q.IsZero then raise(System.DivideByZeroException())
    let g = gcd q p
    fixSign(p/g, q/g)

  member __.Numerator = p
  member __.Denominator = q

  static member (+) (m: Rational, n: Rational) =
    Rational(m.Numerator*n.Denominator + n.Numerator*m.Denominator,
             m.Denominator*n.Denominator)

  static member (-) (m: Rational, n: Rational) =
    Rational(m.Numerator*n.Denominator - n.Numerator*m.Denominator,
             m.Denominator*n.Denominator)

  static member (*) (m: Rational, n: Rational) =
    Rational(m.Numerator*n.Numerator, m.Denominator*n.Denominator)

  static member (/) (m: Rational, n: Rational) =
    Rational(m.Numerator*n.Denominator, m.Denominator*n.Numerator)

In practice, we are likely to want more functionality such as support for equality, comparison, hashing and pretty printing as well as helper functions like an extra constructor that allows ordinary int arguments. The following implementation provides all of these capabilities:

[<StructuredFormatDisplayAttribute("{AsString}")>]
type Rational(p: BigInteger, q: BigInteger) =
  let rec gcd a (b: BigInteger) =
    if b.IsZero then a else
      gcd b (a % b)

  let fixSign(p: BigInteger, q: BigInteger) =
    if q.Sign > 0 then p, q else -p, -q

  let p, q =
    if q.IsZero then raise(System.DivideByZeroException())
    let g = gcd q p
    fixSign(p/g, q/g)

  new(p: int, q: int) = Rational(BigInteger p, BigInteger q)

  member __.Numerator = p
  member __.Denominator = q

  override __.ToString() =
    if q.IsOne then p.ToString() else sprintf "%A/%A" p q

  interface System.IEquatable<Rational> with
    member q1.Equals q2 =
      q1.Numerator = q2.Numerator &&
        q1.Denominator = q2.Denominator

  override q1.Equals q2 =
    (q1 :> System.IEquatable<_>).Equals(q2 :?> Rational)

  interface System.IComparable<Rational> with
    member q1.CompareTo q2 =
      compare
        (q1.Numerator * q2.Denominator)
        (q2.Numerator * q1.Denominator)

  interface System.IComparable with
    member q1.CompareTo q2 =
      (q1 :> System.IComparable<_>).CompareTo(q2 :?> Rational)

  member q.AsString = q.ToString()

  override q.GetHashCode() = hash(q.Numerator, q.Denominator)

  static member (+) (m: Rational, n: Rational) =
    Rational(m.Numerator*n.Denominator + n.Numerator*m.Denominator,
             m.Denominator*n.Denominator)

  static member (-) (m: Rational, n: Rational) =
    Rational(m.Numerator*n.Denominator - n.Numerator*m.Denominator,
             m.Denominator*n.Denominator)

  static member (*) (m: Rational, n: Rational) =
    Rational(m.Numerator*n.Numerator, m.Denominator*n.Denominator)

  static member (/) (m: Rational, n: Rational) =
    Rational(m.Numerator*n.Denominator, m.Denominator*n.Numerator)

An even more comprehensive solution might want to provide parsing from the fractional form (e.g. 2/3) and perhaps even from decimal notation.

Let’s have a look at some examples. The fraction 5/10 is simplified to:

> Rational(5, 10);;
val it : Rational = 1/2

We can multiple ½ by 2/3 to obtain 1/3:

> Rational(1, 2) * Rational(2, 3);;
val it : Rational = 1/3

We can divide ½ by 2/3 to obtain ¾:

> Rational(1, 2) / Rational(2, 3);;
val it : Rational = 3/4

And we can compare rationals, in this case observing that 2/5>1/3:

> compare (Rational(2, 5)) (Rational(1, 3));;
val it : int = 1

Rational numbers are provided by the F# PowerPack which is compatible with our own F# for Numerics and F# for Visualization libraries. For example, see the visualization of a matrix of rationals.

No comments: