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.

Advertisements

29 thoughts on “The dedoublifier, part two

  1. Your “ToString” method can be shortened to:

    public override String ToString() =>
    FormattableString.Invariant($”{Numerator:R}/{Denominator:R}”);

  2. Some are still way over my head at this point, but I very much enjoy these articles. It’s sort of amazing how much variation in competency that exists between programmers. While many I work with are comfortable with simply utilizing various libraries, I am always interested in what is actually going on behind the scenes.

    Keep up the interesting articles.

    • Thanks! Part of the point of this blog is to advance the thesis that there is no magic in those libraries. They were written by people who had to make design decisions every step of the way.

  3. If you did want to simplify the denominator < 0 check, rather than mutating variables you could just do:

    return new Rational(denominator.Sign*numerator/gcd, denominator.Sign*denominator/gcd);

  4. When dealing with 0 denominator shouldn’t the exception be:
    var divEx = new DivideByZeroException();
    throw new ArgumentException(divEx.Message, “denominator”, divEx);
    You know, the DivideByZeroException doesn’t have a paramName property.

    Or maybe, doesn’t throw an exception at all, instead take 0/0 as NaN, 1/0 and -1/0 could be positive and negative infinity as well.

    • I suppose it could be, but in the case of a clear “boneheaded” exception — where if the exception is thrown, the caller has a bug — I am not inclined to spend a lot of time worrying about these subtleties.

      The problem with allowing NaN and Infinity semantics, as doubles and floats do, is that you then open up a whole nother can of worms. Are two infinities equal to each other? Is NaN equal to anything? Suppose you are sorting a list of rationals that contains a NaN — does it sort to the beginning or the end?

      Moreover, doing so violates the “it does what it says on the tin” principle. My class is called “Rational”. NaN and infinity are not rational numbers.

      • If a type does not support trap values, then it makes sense to say that every operation must yield a valid value or trap. If, however, a type does support trap values, then it makes sense to have invalid operations yield a trap value, and have trap if/when code attempts to use a trap values in illegitimate ways (invoking on a trap value an operation which can yield another would simply do so; invoking an operation which can’t (such as a comparison which is required to yield true or false) would trap. If a type includes an IsTrapValue method, such an approach will allows code which is prepared for trap values to use them more smoothly than if operations on them throw exceptions, but will automatically trap if code isn’t prepared for them.

        If the default value of the type behaved as a numerical zero, it would be reasonable for the type not to have trap values. If the default representation is a trap value, however, that implies that the type supports trap values, which would in turn suggest that returning a trap value in many cases may be preferable to throwing an immediate exception.

      • When working at MS did you had guidelines of which exceptions to throw in each case? When writing libraries I always get confused about what exceptions to throw when validating parameters, usually I look at existing classes for something similar, but in a few cases two .Net framework classes throws two different exceptions for the same error and in other few cases the exception type is a somewhat unexpected.

        BTW, I am guessing what you will do to get the original fraction back in part III but holding anxiety to not spoil it, please, don’t take to long to publish it.

  5. I admit I haven’t thought about this in a while, but isn’t it conventional to think of the exponent as the shift from the most-significant bit of the mantissa, not the least-significant bit?

    I would expect the value of a float with an exponent of “0” to be “1.mantissa”, not “1mantissa.” (excluding zero, of course).

  6. Why not treat 0/0 as NaN, 1/0 as +Inf, -1/0 as -Inf, 0/1 as +0 and 0/-1 as -0? This way all double values will be handled properly (with the exception of NaNs with payloads).

    • Because those semantics of double are *horrid*. I don’t want to replicate them. The tin says “rational” on it, and it makes sense that the contents of that tin are the rational numbers, not the rational numbers where there are two zeros plus two points at infinity and a value that is not comparable to any other value. When I write a class called Rational it means rational numbers, neither more nor less.

  7. I’m a little confused by the % operator. I suppose if I had to present an implementation, that would be the most reasonable, but I don’t have a good reason to expect any particular behavior without the code in front of me.
    I don’t think I’ve seen modulus applied to non-integers. Plus this doesn’t really fit the Euclidean division algorithm formula (a = bq + r) in a way I’d expect; if you set (q = a/b), r would always be 0 with these rationals.

  8. It should be ArgumentOutOfRangeException, not DivideByZeroException. The reason is that (operators aside), the latter would lead the caller to believe it’s a bug in YOUR code. ArgumentException clearly indicates that it’s a bug in the caller’s code.

  9. > I decided to go for the logical one, but I could be argued into the other position.

    I immediately spotted this when reading the code. I consider DivideByZeroException to be one of the intrinsic exceptions such as NRE that should never be thrown and are always to be regarded a bug by convention (a bug in the code that produces it).

  10. Pingback: The dedoublifier, part three | Fabulous adventures in coding

  11. Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1985

  12. Pingback: The week in .NET - 12/15/2015 - .NET Blog - Site Home - MSDN Blogs

  13. Pingback: 주간닷넷 2015년 12월 15일 - Korea Evangelist - Site Home - MSDN Blogs

  14. Hey Eric, why do you write ‘else’ for your ‘if’s when you are going to throw if the ‘if’ is true?

    for instance:

    if (denominator == 0)
    throw new DivideByZeroException();
    else if (numerator == 0)
    return new Rational(0, 1);

    instead of

    if (denominator == 0)
    throw new DivideByZeroException();
    if (numerator == 0)
    return new Rational(0, 1);

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s