The dedoublifier, part two

A couple of years ago I developed my own arbitrary precision natural number and integer mathematics types, just for fun and to illustrate how it could be done. I'm going to do the same for rational numbers here, but rather than using my integer type, I'll just use the existing BigInteger type to represent the numerator and denominator. Either would do just fine.

Of course I could have used some existing BigRational types but for various reasons that I might go into in a future blog article, I decided it would be more interesting to simply write my own. Let's get right to it; I'll annotate the code as I go.

public struct Rational : IComparable<Rational>, IEquatable<Rational>{ public BigInteger Numerator { get; } public BigInteger Denominator { get; } private Rational(BigInteger numerator, BigInteger denominator) { Numerator = numerator; Denominator = denominator; }

Already we have some design decisions. First off, a rational is a struct. It seems reasonable that it be a value type, since it represents an immutable value.

There were other interfaces I could have implemented, like the legacy non-generic IComparable but hey, those are easy to add if you need them and I'm not trying to develop a fully functional library here.

Obviously a rational is an immutable pair of integers.

I've made the constructor private; we'll build these things up from factory methods that ensure two invariants: first that the denominator is non-zero and positive, and second, that the fraction is in its simplest form.

I should probably have an assertion to this effect in the code here, to catch any bugs I make in the future.

Unfortunately the code I present will violate this design decision in one way; default(Rational) will be 0/0, which is not legal. It would be very nice if the default value were zero; a good guideline is to ensure that default values of structs are meaningful. I could achieve this in a few ways; probably the easiest would be to make the denominator a more complex property that detects when it is zero and returns one instead. I'm going to ignore this little wrinkle; almost any use of a default struct will produce an exception.

public static Rational FromIntegers( BigInteger numerator, BigInteger denominator){ if (denominator == 0) throw new DivideByZeroException(); else if (numerator == 0) return new Rational(0, 1); // Neither is zero. // We wish to ensure the fraction is in its simplest form. // Note that the GCD is always positive. BigInteger gcd = BigInteger.GreatestCommonDivisor( numerator, denominator); // We ensure the denominator is always positive. return new Rational( denominator.Sign * numerator / gcd, denominator.Sign * denominator / gcd);}

This is our straightforward factory method. The only oddity here is that I was not quite sure if the exception should be a divide by zero, which is what it logically is, or an invalid argument, which is what it actually is. I decided to go for the logical one, but I could be argued into the other position.

A subtle point here: some people would write the code

 if (denominator < 0) { denominator = -denominator; numerator = - numerator; } return new Rational(numerator/gcd, denominator/gcd);

That's a reasonable choice, but I personally prefer to eliminate variable mutations whenever possible. Mutations are points where the code becomes less understandable and less debugable because knowledge of the past is lost. I particularly wish to not mutate parameters because then things get really hard to debug; I cannot glance at the code in the debugger and know what values were passed in. I wish C# had "final" parameters that could not be mutated, the same way that the variable in a using or foreach cannot be mutated by the user.

(Thanks to commenter Alex Godofsky for improving the code above.)

Now we come to an interesting one:

static public Rational FromDouble(double value){ DoubleHelper d = new DoubleHelper(value); if (d.IsNaN) throw new ArgumentException("Not a number", "value"); else if (d.IsInfinity) throw new ArgumentException("Not a finite number", "value"); else if (d.IsZero) return 0; BigInteger numerator; BigInteger denominator; if (d.Exponent >= 0) { numerator = d.Sign * d.Mantissa * BigInteger.Pow(2, d.Exponent); denominator = 1; } else { numerator = d.Sign * d.Mantissa; denominator = BigInteger.Pow(2, -d.Exponent); } return FromIntegers(numerator, denominator);}

We start by throwing out weird doubles like NaN and infinities. If the double is zero then we return the rational 0/1; an implicit conversion from int to Rational later on makes this work. This is an unnecessary early-out; the code below would produce the correct result, but it also seems nice to skip the complicated code if we know we are in a special case.

The math is straightforward. If the exponent is a positive number then we simply raise two to that power and multiply the mantissa by it. If it is a negative number then this increases the denominator.

We might not be in simplest form at this point, but the other factory called at the end there deals with it.

Everything from this point on is super boring.

public int Sign => Numerator.Sign;public BigInteger WholePart => Numerator / Denominator;public Rational FractionalPart => new Rational(Numerator % Denominator, Denominator);public Rational AbsoluteValue => Sign < 0 ? -this : this;

No surprises here. One small design point: it seems reasonable that the sign is a "property" of a rational. But is the absolute value more like a property - like the color of an apple - or more like a function whose input is a particular rational? I considered making the absolute value a method, but ultimately decided that it was enough like a property of the value to be written as a property.

All of the arithmetic, comparison and conversion operations are similarly trivial:

public static bool operator <(Rational x, Rational y) => CompareTo(x, y) < 0;public static bool operator >(Rational x, Rational y) => CompareTo(x, y) > 0;public static bool operator <=(Rational x, Rational y) => CompareTo(x, y) <= 0;public static bool operator >=(Rational x, Rational y) => CompareTo(x, y) >= 0;public static bool operator ==(Rational x, Rational y) => CompareTo(x, y) == 0;public static bool operator !=(Rational x, Rational y) => CompareTo(x, y) != 0;

Again, though I was initially skeptical I am now loving how compact the code is for these trivial methods in C# 6.

public static Rational operator +(Rational r) => r;public static Rational operator -(Rational r) => new Rational(-r.Numerator, r.Denominator);public static Rational operator +(Rational r1, Rational r2) => FromIntegers( r1.Numerator * r2.Denominator + r1.Denominator * r2.Numerator, r1.Denominator * r2.Denominator);public static Rational operator -(Rational r1, Rational r2) => r1 + (-r2);public static Rational operator *(Rational r1, Rational r2) => FromIntegers( r1.Numerator * r2.Numerator, r1.Denominator * r2.Denominator);public static Rational operator /(Rational r1, Rational r2) => FromIntegers( r1.Numerator * r2.Denominator, r1.Denominator * r2.Numerator);public static Rational operator %(Rational r1, Rational r2) => FromIntegers( (r1.Numerator*r2.Denominator) % (r1.Denominator*r2.Numerator), r1.Denominator * r2.Denominator);public static implicit operator Rational(BigInteger value) => FromIntegers(value, 1);public static implicit operator Rational(int value) => FromIntegers(value, 1);public static implicit operator Rational(long value) => FromIntegers(value, 1);public override bool Equals(object obj) => (obj is Rational) && (CompareTo(this, (Rational)obj) == 0);public override int GetHashCode() => Numerator.GetHashCode() + 17 * Denominator.GetHashCode();public override String ToString() => FormattableString.Invariant ($"{Numerator:R}/{Denominator:R}");public int CompareTo(Rational x) => CompareTo(this, x);public bool Equals(Rational x) => CompareTo(this, x) == 0;public static int CompareTo(Rational x, Rational y) => (x - y).Sign;

And that is that. We can now do arbitrary arithmetic on rationals, and convert from doubles to the exact rational value the double represents.

Why were we doing this in the first place? Oh yeah, because I wanted to take an arbitrary double that represented a fraction, and turn it back into that fraction. Next time on FAIC: we'll do that.