# Rob Blackbourn

## Overview

The following code implements a rational number.

## The code

I have split the code into partial classes to keep the functionality distinct.

For the underlying types I have decided to use longs throughout as the main problem with rational numbers is overflow. Furthermore I have chosen to always reduce the fraction. This adds an overhead on each computation, but contains overflow problems.

### Algorithms

The first task is to write the greatest common divisor function. From my previous post I have established the Euclid modulus function to be the fastest.

```namespace JetBlack.Common
{
public static class Algorithms
{
public static long Gcd(long a, long b)
{
bool aneg = a < 0, bneg = b < 0;
if (aneg) a = -a;
if (bneg) b = -b;

var gcd = Gcd((ulong)a, (ulong)b);
return aneg == bneg ? (long)gcd : -((long)gcd);
}

public static ulong Gcd(ulong a, ulong b)
{
while (a != 0 && b != 0)
{
if (a > b)
a %= b;
else
b %= a;
}

return a == 0 ? b : a;
}
}
}
```

### The Main Class

The class is actually a struct, which is a common choice for number style classes to reduce garbage collection issues during computation. Unfortunately it is not possible to defeat the default initialiser, so invalid fractions (where the denominator is 0) can be built. I could have added a check for this in the arithmetic code, but as all functions pass through the constructor (which throws said exception) I have chosen not to.

I wanted to be able to express the number both as a simple fraction and as a whole and fractional part. For example "3/2" or "1 1/2". The format string "S" is for the simple style and "L" for the longer. The standard integer format strings return the whole part, and the floating point format strings work on the floating point representation.

```using System;
using System.Globalization;

namespace JetBlack.Common
{
public partial struct Rational : IEquatable<Rational>, IFormattable
{
public Rational(long numerator, long denominator = 1) : this()
{
if (denominator == 0) throw new ArgumentOutOfRangeException("denominator", "The denominator cannot be 0.");

Initialise(numerator, denominator);
}

private void Initialise(long numerator, long denominator)
{
if (denominator == 1)
{
Numerator = numerator;
Denominator = 1;
}
else if (numerator == denominator)
{
Numerator = 1;
Denominator = 1;
}
else if (numerator == 0)
{
Numerator = 0;
Denominator = 1;
}
else
{
var gcd = Algorithms.Gcd(numerator, denominator);
numerator /= gcd;
denominator /= gcd;
Numerator = denominator < 0 ? -numerator : numerator;
Denominator = denominator < 0 ? -denominator : denominator;
}
}

public long Numerator { get; private set; }
public long Denominator { get; private set; }

public bool IsValid
{
get { return Denominator != 0; }
}

public static Rational Empty { get; private set; }
public static Rational Zero { get; private set; }
public static Rational One { get; private set; }

static Rational()
{
Empty = new Rational();
Zero = new Rational(0);
One = new Rational(1);
}

public bool Equals(Rational other)
{
return Numerator == other.Numerator && Denominator == other.Denominator;
}

public override bool Equals(object obj)
{
return obj is Rational && Equals((Rational) obj);
}

public override int GetHashCode()
{
unchecked
{
return (Numerator.GetHashCode() * 397) ^ Denominator.GetHashCode();
}
}

public override string ToString()
{
}

public string ToString(string format, IFormatProvider provider)
{
if (string.IsNullOrWhiteSpace(format))
format = "L";

switch (format)
{
case 'S':
case 's':
return string.Concat(Numerator, '/', Denominator);

case 'L':
case 'l':
if (Denominator == 1)
return Numerator.ToString(CultureInfo.InvariantCulture);

if ((Numerator >= 0 && Numerator < Denominator) || (Numerator < 0 && -Numerator < Denominator))
return string.Concat(Numerator, '/', Denominator);

if (Numerator < 0)
return string.Concat(Numerator / Denominator, ' ', -Numerator % Denominator, '/', Denominator);

return string.Concat(Numerator / Denominator, ' ', Numerator % Denominator, '/', Denominator);

case 'D':
case 'd':
case 'X':
case 'x':
case 'N':
case 'n':
return (Numerator / Denominator).ToString(format, provider);

case 'C':
case 'c':
case 'E':
case 'e':
case 'F':
case 'f':
case 'G':
case 'g':
case 'P':
case 'p':
case 'R':
case 'r':
return ((double) Numerator / Denominator).ToString(format, provider);

default:
throw new FormatException(string.Concat("Unknown format string: \"", format, "\"."));
}
}
}
}
```

### Arithmetic

The arithmetic is fairly orthodox, with the exception of the checked keyword. This will report overflow to the consumer which I felt desirable.

The add routine checks for the same denominator to reduce overflows, with the cost of the check.

A "Round" function is implemented. This takes a list of valid denominators, and expresses the fraction using the closest specified denominator.

```using System.Collections.Generic;

namespace JetBlack.Common
{
public partial struct Rational
{
public Rational Negate()
{
return new Rational(-Numerator, Denominator);
}

public Rational Invert()
{
return new Rational(Denominator, Numerator);
}

{
}

{
checked
{
}
}

public Rational Subtract(Rational rational)
{
}

public Rational Subtract(long value)
{
checked
{
}
}

public Rational Multiply(Rational rational)
{
return Multiply(rational.Numerator, rational.Denominator);
}

public Rational Multiply(long value)
{
checked
{
return Multiply(value * Denominator, Denominator);
}
}

public Rational Divide(Rational rational)
{
return Multiply(rational.Denominator, rational.Numerator);
}

public Rational Divide(long value)
{
checked
{
return Multiply(Denominator, value * Denominator);
}
}

private Rational Add(long numerator, long denominator)
{
checked
{
return
Denominator == denominator
? new Rational(Numerator + numerator, denominator)
: new Rational(Numerator * denominator + numerator * Denominator, Denominator * denominator);
}
}

private Rational Multiply(long numerator, long denominator)
{
checked
{
return new Rational(Numerator * numerator, Denominator * denominator);
}
}

public Rational Abs()
{
return Numerator < 0 ? new Rational(-Numerator, Denominator) : this;
}

public Rational Round(IList<long> targetDenominators)
{
var sign = Numerator < 0 ? -1 : 1;
var numerator = Numerator * sign;
var whole = numerator / Denominator;
numerator %= Denominator;
var local = new Rational(numerator, Denominator);
var best = new Rational(0);
var bestError = new Rational(1);

foreach (var denominator in targetDenominators)
{
var d = Denominator / denominator;
var n = numerator / d;
if (n != 0)
{
var guess = new Rational(whole * denominator + n, denominator);
var guessError = (local - guess).Abs();
if (guessError < bestError)
{
best = guess;
bestError = guessError;
}
}
}

return best;
}
}
}
```

### Implementing IComparable

This contains a number of tweaks. If the denominators are the same I don't need to normalise. Rather than simply check the normalised representations, I first check the whole number. Only if that is the same is the fractional part examined. This should reduce overflow problems.

```using System;

namespace JetBlack.Common
{
public partial struct Rational : IComparable<Rational>, IComparable
{
public int CompareTo(Rational other)
{
long diff;

if (Denominator == other.Denominator)
diff = Numerator - other.Numerator;
else
{
var whole1 = Numerator / Denominator;
var whole2 = other.Numerator / other.Denominator;
diff = whole1 - whole2;

if (diff == 0)
{
var n1 = Numerator % Denominator;
var n2 = other.Numerator % other.Denominator;

checked
{
diff = n1 * other.Denominator - n2 * Denominator;
}
}
}

return diff == 0 ? 0 : diff > 0 ? 1 : -1;
}

public int CompareTo(object value)
{
if (value == null)
return 1;
if (!(value is Rational))
throw new ArgumentException("must be rational");

return CompareTo((Rational) value);
}
}
}
```

### Implementing IConvertable

Not much to talk about here. I'm not sure what to do about the "GetTypeCode" method.

```using System;

namespace JetBlack.Common
{
public partial struct Rational : IConvertible
{
public TypeCode GetTypeCode()
{
throw new InvalidOperationException();
}

public bool ToBoolean(IFormatProvider provider)
{
return Numerator != 0;
}

public char ToChar(IFormatProvider provider)
{
throw new InvalidCastException("no valid cast to char");
}

public sbyte ToSByte(IFormatProvider provider)
{
return (sbyte) (Numerator / Denominator);
}

public byte ToByte(IFormatProvider provider)
{
return (byte)(Numerator / Denominator);
}

public short ToInt16(IFormatProvider provider)
{
return (short)(Numerator / Denominator);
}

public ushort ToUInt16(IFormatProvider provider)
{
return (ushort)(Numerator / Denominator);
}

public int ToInt32(IFormatProvider provider)
{
return (int)(Numerator / Denominator);
}

public uint ToUInt32(IFormatProvider provider)
{
return (uint)(Numerator / Denominator);
}

public long ToInt64(IFormatProvider provider)
{
return Numerator / Denominator;
}

public ulong ToUInt64(IFormatProvider provider)
{
return (ulong)(Numerator / Denominator);
}

public float ToSingle(IFormatProvider provider)
{
return (float)((double)Numerator / Denominator);
}

public double ToDouble(IFormatProvider provider)
{
return (double)Numerator / Denominator;
}

public decimal ToDecimal(IFormatProvider provider)
{
return (decimal)Numerator / Denominator;
}

public DateTime ToDateTime(IFormatProvider provider)
{
throw new InvalidCastException("no valid cast to DateTime");
}

public string ToString(IFormatProvider provider)
{
}

public object ToType(Type type, IFormatProvider provider)
{
switch (Type.GetTypeCode(type))
{
case TypeCode.Boolean:
case TypeCode.Char:
case TypeCode.SByte:
case TypeCode.Byte:
case TypeCode.Int16:
case TypeCode.UInt16:
case TypeCode.Int32:
case TypeCode.UInt32:
case TypeCode.Int64:
case TypeCode.UInt64:
case TypeCode.Single:
case TypeCode.Double:
case TypeCode.Decimal:
case TypeCode.DateTime:
case TypeCode.String:
default:
throw new InvalidCastException("no valid cast to " + type.Name);
}
}
}
}
```

### The Operators

The operators work as expected. I have decided not to add an "int" specific operator, as they convert implicitly to "long" anyway.

```namespace JetBlack.Common
{
public partial struct Rational
{
public static Rational operator -(Rational a)
{
return a.Negate();
}

public static Rational operator +(Rational a, Rational b)
{
}

public static Rational operator +(Rational a, long b)
{
}

public static Rational operator +(long a, Rational b)
{
}

public static Rational operator ++(Rational a)
{
a.Initialise(a.Numerator + a.Denominator, a.Denominator);
return a;
}

public static Rational operator -(Rational a, Rational b)
{
return a.Subtract(b);
}

public static Rational operator -(Rational a, long b)
{
return a.Subtract(b);
}

public static Rational operator -(long a, Rational b)
{
}

public static Rational operator --(Rational a)
{
a.Initialise(a.Numerator - a.Denominator, a.Denominator);
return a;
}

public static Rational operator *(Rational a, Rational b)
{
return a.Multiply(b);
}

public static Rational operator *(Rational a, long b)
{
return a.Multiply(b);
}

public static Rational operator *(long a, Rational b)
{
return b.Multiply(a);
}

public static Rational operator /(Rational a, Rational b)
{
return a.Divide(b);
}

public static Rational operator /(Rational a, long b)
{
return a.Divide(b);
}

public static Rational operator /(long a, Rational b)
{
return b.Invert().Multiply(a);
}

public static bool operator ==(Rational a, Rational b)
{
return a.Equals(b);
}

public static bool operator !=(Rational a, Rational b)
{
return !a.Equals(b);
}

public static bool operator >(Rational a, Rational b)
{
return a.CompareTo(b) > 0;
}

public static bool operator >=(Rational a, Rational b)
{
return a.CompareTo(b) >= 0;
}

public static bool operator <(Rational a, Rational b)
{
return a.CompareTo(b) < 0;
}

public static bool operator <=(Rational a, Rational b)
{
return a.CompareTo(b) <= 0;
}

public static implicit operator Rational(long value)
{
return new Rational(value);
}

public static explicit operator long(Rational value)
{
return value.Numerator / value.Denominator;
}

public static explicit operator double(Rational value)
{
return (double)value.Numerator / value.Denominator;
}

public static explicit operator Rational(double value)
{
return FromDouble(value, 8);
}
}
}
```

### Parsing

The routine works for both the simple and long representation.

```using System;

namespace JetBlack.Common
{
public partial struct Rational
{
public static Rational Parse(string s)
{
if (s == null) throw new ArgumentNullException();

Rational rational;
if (!TryParse(s, out rational)) throw new FormatException();
return rational;
}

public static bool TryParse(string s, out Rational rational)
{
if (s != null)
{
s = s.Trim();
var slashIndex = s.IndexOf('/');
if (slashIndex == -1)
{
long whole;
if (long.TryParse(s, out whole))
{
rational = new Rational(whole);
return true;
}
}
else
{
var denominatorString = s.Substring(slashIndex + 1, s.Length - (slashIndex + 1)).TrimStart();
long denominator;
if (long.TryParse(denominatorString, out denominator))
{
long numerator;
var numeratorString = s.Substring(0, slashIndex).TrimEnd();
var spaceIndex = numeratorString.IndexOf(' ');
if (spaceIndex == -1)
{
if (long.TryParse(numeratorString, out numerator))
{
rational = new Rational(numerator, denominator);
return true;
}
}
else
{
long whole;
if (long.TryParse(numeratorString.Substring(0, spaceIndex).TrimEnd(), out whole)
&& long.TryParse(numeratorString.Substring(spaceIndex + 1, numeratorString.Length - spaceIndex - 1).TrimStart(), out numerator)
&& numerator >= 0)
{
rational = new Rational(whole * denominator + numerator, denominator);
return true;
}
}
}
}
}
rational = default(Rational);
return false;
}
}
}
```

### Utilities

This routine was mercilessly ripped from the web. It seems to be the most concise and complete solution, though perhaps not the fastest. I considered completeness and simplicity more important as my use cases will typically be parsing from an external input.

```using System;

namespace JetBlack.Common.Numerics
{
public partial struct Rational
{
public static Rational FromDouble(double value, int maxIterations = int.MaxValue, double threshold = double.Epsilon)
{
var whole = (long)Math.Floor(value);
value -= whole;

if (value < threshold)
return new Rational(whole);

if (1 - threshold < value)
return new Rational(whole + 1);

var low = new Rational(0);
var high = new Rational(1);

for (var i = 0; i < maxIterations; ++i)
{
var mid = new Rational(low.Numerator + high.Numerator, low.Denominator + high.Denominator);
if (mid.Numerator > mid.Denominator * (value + threshold))
high = mid;
else if (mid.Numerator < mid.Denominator * (value - threshold))
low = mid;
else
return new Rational(whole * mid.Denominator + mid.Numerator, mid.Denominator);
}

throw new ArithmeticException("Failed to solve.");
}
}
}
```

### The tests

The following code tests the implementation.

```using System;
using System.Diagnostics;
using NUnit.Framework;

namespace JetBlack.Common.Test
{
[TestFixture]
public class RationalFixture
{
[Test]
public void TestContructor()
{
var r0 = new Rational();

var f1 = new Rational(2, 4);
Assert.AreEqual(1, f1.Numerator);
Assert.AreEqual(2, f1.Denominator);

var f2 = new Rational(2, -4);
Assert.AreEqual(-1, f2.Numerator);
Assert.AreEqual(2, f2.Denominator);

var f3 = new Rational(10, 2);
Assert.AreEqual(5, f3.Numerator);
Assert.AreEqual(1, f3.Denominator);

var f4 = new Rational(-10, 2);
Assert.AreEqual(-5, f4.Numerator);
Assert.AreEqual(1, f4.Denominator);

var f5 = new Rational(10, -2);
Assert.AreEqual(-5, f5.Numerator);
Assert.AreEqual(1, f5.Denominator);

var f6 = new Rational(-10, -2);
Assert.AreEqual(5, f6.Numerator);
Assert.AreEqual(1, f6.Denominator);

var f7 = new Rational(0, 10);
Assert.AreEqual(0, f7.Numerator);
Assert.AreEqual(1, f7.Denominator);

var f8 = new Rational(0);
Assert.AreEqual(0, f8.Numerator);
Assert.AreEqual(1, f8.Denominator);

var f9 = new Rational(0, -10);
Assert.AreEqual(0, f9.Numerator);
Assert.AreEqual(1, f9.Denominator);

var f10 = new Rational(5);
Assert.AreEqual(5, f10.Numerator);
Assert.AreEqual(1, f10.Denominator);

Assert.Throws<ArgumentOutOfRangeException>(() => new Rational(1, 0));
}

[Test]
public void TestParse()
{
Rational rational;

Assert.IsTrue(Rational.TryParse("123", out rational));
Assert.AreEqual(new Rational(123), rational);
Debug.WriteLine(rational);

Assert.IsTrue(Rational.TryParse("123/456", out rational));
Assert.AreEqual(new Rational(123, 456), rational);

Assert.IsTrue(Rational.TryParse("123 456/789", out rational));
Assert.AreEqual(new Rational(123*789 + 456, 789), rational);

Assert.IsTrue(Rational.TryParse("-123", out rational));
Assert.AreEqual(new Rational(-123), rational);

Assert.IsTrue(Rational.TryParse("-123/456", out rational));
Assert.AreEqual(new Rational(-123, 456), rational);

Assert.IsTrue(Rational.TryParse("-123 456/789", out rational));
Assert.AreEqual(new Rational(-123 * 789 + 456, 789), rational);

Assert.IsTrue(Rational.TryParse(" \t 123\t\t  \t", out rational));
Assert.AreEqual(new Rational(123), rational);
Debug.WriteLine(rational);

Assert.IsTrue(Rational.TryParse(" \t123\t/ 456   \t", out rational));
Assert.AreEqual(new Rational(123, 456), rational);

Assert.IsTrue(Rational.TryParse("   123     456  /   789   ", out rational));
Assert.AreEqual(new Rational(123 * 789 + 456, 789), rational);

Assert.IsTrue(Rational.TryParse("  -123   ", out rational));
Assert.AreEqual(new Rational(-123), rational);

Assert.IsTrue(Rational.TryParse("  -123  /   456  ", out rational));
Assert.AreEqual(new Rational(-123, 456), rational);

Assert.IsTrue(Rational.TryParse("   -123    456   /   789  ", out rational));
Assert.AreEqual(new Rational(-123 * 789 + 456, 789), rational);
}

[Test]
{
var result = new Rational(1, 2) + new Rational(1, 4);
Assert.AreEqual(new Rational(3, 4), result);

result = new Rational(1, 2) + 1;
Assert.AreEqual(new Rational(3, 2), result);

result = 2 + new Rational(1, 2);
Assert.AreEqual(new Rational(5, 2), result);

Assert.Throws<OverflowException>(() =>
{
result = new Rational(1) + long.MaxValue;
});
}

[Test]
public void TestSubtract()
{
var result = new Rational(1, 2) - new Rational(1, 4);
Assert.AreEqual(new Rational(1, 4), result);

result = new Rational(1, 2) - 1;
Assert.AreEqual(new Rational(-1, 2), result);

result = 2 - new Rational(1, 2);
Assert.AreEqual(new Rational(3, 2), result);

Assert.Throws<OverflowException>(() =>
{
result = new Rational(-1) - long.MinValue;
});
}

[Test]
public void TestMultiply()
{
var result = new Rational(1, 2) * new Rational(1, 4);
Assert.AreEqual(new Rational(1, 8), result);

result = new Rational(1, 2) * 2;
Assert.AreEqual(new Rational(1), result);

result = 3 * new Rational(1, 4);
Assert.AreEqual(new Rational(3, 4), result);

Assert.Throws<OverflowException>(() =>
{
result = new Rational(2) * long.MaxValue;
});
}

[Test]
public void TestDivide()
{
var result = new Rational(1, 2) / new Rational(1, 4);
Assert.AreEqual(new Rational(2), result);

result = new Rational(1, 2) / 2;
Assert.AreEqual(new Rational(1, 4), result);

result = 3 / new Rational(1, 4);
Assert.AreEqual(new Rational(12), result);

Assert.Throws<OverflowException>(() =>
{
result = new Rational(1, long.MaxValue) / long.MaxValue;
});
}

[Test]
public void TestCast()
{
Rational f1 = 5;
Assert.AreEqual(5, f1.Numerator);
Assert.AreEqual(1, f1.Denominator);

Rational f2 = -5;
Assert.AreEqual(-5, f2.Numerator);
Assert.AreEqual(1, f2.Denominator);

var i1 = (int)new Rational(1, 2);
Assert.AreEqual(0, i1);

var i2 = (int)new Rational(3, 2);
Assert.AreEqual(1, i2);

var d1 = (double)new Rational(1, 2);
Assert.AreEqual(0.5, d1, 0.0000001);

var d2 = (double)new Rational(3, 2);
Assert.AreEqual(1.5, d2, 0.0000001);

var d3 = (double)new Rational(1, 3);
Assert.AreEqual(0.3333333333333, d3, 0.0000001);

var f3 = Rational.FromDouble(0.5, 8);

var f4 = Rational.FromDouble(1.0/3.0, 8);
Assert.AreEqual(1, f4.Numerator);
Assert.AreEqual(3, f4.Denominator);

var f5 = Rational.FromDouble(1.0 / 2.0, 8);
Assert.AreEqual(1, f5.Numerator);
Assert.AreEqual(2, f5.Denominator);
}

[Test]
public void TestRound()
{
var validDenominators = new[] {2L, 3L, 4L, 5L, 6L, 8L, 12L, 16L};

var oneThird = new Rational(1, 3);
var almostOneThird = oneThird + new Rational(1, 100000);
Assert.AreEqual(oneThird, almostOneThird.Round(validDenominators));

var oneFifth = new Rational(1, 5);
var almostOneFifth = oneFifth + new Rational(1, 100000);
Assert.AreEqual(oneFifth, almostOneFifth.Round(validDenominators));

var oneHalf = new Rational(1, 2);
var almostOneHalf = oneHalf + new Rational(1, 100000);
Assert.AreEqual(oneHalf, almostOneHalf.Round(validDenominators));
}

[Test]
public void TestPreIncrement()
{
var r1 = new Rational(1, 7);
var r2 = ++r1;
Assert.AreEqual(8, r1.Numerator);
Assert.AreEqual(7, r1.Denominator);
Assert.AreEqual(8, r2.Numerator);
Assert.AreEqual(7, r2.Denominator);
}

[Test]
public void TestPostIncrement()
{
var r1 = new Rational(1, 7);
var r2 = r1++;
Assert.AreEqual(8, r1.Numerator);
Assert.AreEqual(7, r1.Denominator);
Assert.AreEqual(1, r2.Numerator);
Assert.AreEqual(7, r2.Denominator);
}
}
}
```

Print | posted on Friday, November 14, 2014 11:02 AM | Filed Under [ C# rational fraction ]

### Feedback ## #re: A Rational Number Class in C#

How to implement of rational numbers
3/23/2016 6:10 AM | Kandiban ## #re: A Rational Number Class in C#

how to implement of rational numbers
3/23/2016 6:12 AM | Kesavan