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.

Wednesday, 28 August 2013

Optimizing k-nucleotide

The F#.NET Journal just published an article about optimization:
"The Computer Language Benchmarks Game contains solutions to many problems written in many different languages. This article walks through the design and implementation of a solution to the k-nucleotide problem that is 3.6x faster than the solution listed on that site at the time of writing..."
To read this article and more, subscribe to The F#.NET Journal today!

Wednesday, 14 August 2013

F# vs OCaml part 2: equality and modules

The F#.NET Journal just published an article about metaprogramming:
"Microsoft's F# programming language is a close relative of the OCaml programming language from INRIA. This article is the second in a series comparing and contrasting the two languages and their environments with a focus on the implementations of equality, comparison and hashing as well as OCaml's exotic higher-order module system..."
To read this article and more, subscribe to The F#.NET Journal today!

Monday, 5 August 2013

Implementing Lisp 1.5

The F#.NET Journal just published an article about metaprogramming:
"In 1962, John McCarthy published the definition of Lisp 1.5 whilst at MIT. This article follows that document in order to write a simple Lisp parser and evaluator and studies some example inputs..."
To read this article and more, subscribe to The F#.NET Journal today!

Thursday, 1 August 2013

F# vs OCaml part 1: syntax and types

The F#.NET Journal just published an article about programming languages:
"Microsoft's F# programming language is a close relative of the OCaml programming language from INRIA. This article is the first in a series comparing and contrasting the two languages and their environments with a focus on the basic syntax and type systems in the two languages..."
To read this article and more, subscribe to The F#.NET Journal today!