8
\$\begingroup\$

I have written a Rational struct for working with rational numbers, i.e. Rational(int numerator, int denominator).

A recent post regarding rational numbers peaked my interest. I particular like the answer by @aush with his RationalNumber class. I am inclined to think of a rational number as just that: a number, akin to { int, double, Decimal }. So it screams for struct rather than a class.

Note I am neither a student, nor a teacher. Though I write code for a living, I have no business requirements for Rational, which means I have no constraints or restrictions on the struct design. I am only limited by what I can imagine how a rational number should behave. In fact, I have no foreseen practical need for Rational. I just find that going through such mental exercises helps improve my overall skills.

namespace System
{
    public struct Rational : IComparable, IComparable<Rational>, IEquatable<Rational>
    {
        public int Numerator { get; private set; }
        public int Denominator { get; private set; }

        // These fields bypass Simplify().
        public static readonly Rational MinValue = new Rational { Numerator = int.MinValue, Denominator = 1 };
        public static readonly Rational MaxValue = new Rational { Numerator = int.MaxValue, Denominator = 1 };
        public static readonly Rational Epsilon = new Rational { Numerator = 1, Denominator = int.MaxValue };
        public static readonly Rational Undefined = new Rational { Numerator = 0, Denominator = 0 };
        public static readonly Rational Zero = new Rational { Numerator = 0, Denominator = 1 };
        public static readonly Rational One = new Rational { Numerator = 1, Denominator = 1 };
        public static readonly Rational MinusOne = new Rational { Numerator = -1, Denominator = 1 };

        public Rational(int numerator, int denominator = 1) : this()
        {
            this.Numerator = numerator;
            this.Denominator = denominator;
            // There is a special case where Simplify() could throw an exception:
            //
            //      new Rational(int.MinValue, certainNegativeIntegers)
            //
            // In general, having the contructor throw an exception is bad practice.
            // However given the extremity of this special case and the fact that Rational 
            // is an immutable struct where its inputs are ONLY validated DURING
            // construction, I allow the exception to be thrown here.
            Simplify();
        }

        public static bool TryCreate(int numerator, int denominator, out Rational result)
        {
            try
            {
                result = new Rational(numerator, denominator);
                return true;
            }
            catch
            {
                result = Undefined;
            }
            return false;
        }

        public static bool TryParse(string s, out Rational result)
        {
            try
            {
                result = Rational.Parse(s);
                return true;
            }
            catch
            {
                result = Undefined;
            }
            return false;
        }

        public static Rational Parse(string s)
        {
            // Note that "3 / -4" would return new Rational(-3, 4).
            var tokens = s.Split(new char[] { '/' });

            var numerator = 0;
            var denominator = 0;

            switch (tokens.Length)
            {
                case 1:
                    numerator = GetInteger("Numerator", tokens[0]);
                    denominator = 1;
                    break;
                case 2:
                    numerator = GetInteger("Numerator", tokens[0]);
                    denominator = GetInteger("Denominator", tokens[1]);
                    break;
                default:
                    throw new ArgumentException(string.Format("Invalid input string: '{0}'", s));
            }
            return new Rational(numerator, denominator);
        }

        // This is only called by Parse.
        private static int GetInteger(string desc, string s)
        {
            if (string.IsNullOrWhiteSpace(s))
            {
                throw new ArgumentNullException(desc);
            }
            var result = 0;
            // TODO: Decide whether it's good idea to convert " -  4" to "-4".
            s = s.Replace(" ", string.Empty);
            if (!int.TryParse(s, out result))
            {
                throw new ArgumentException(string.Format("Invalid value for {0}: '{1}'", desc, s));
            }
            return result;
        }

        //TODO: consider other overloads of ToString().  Perhaps one to always display a division symbol.
        // For example, new Rational(0, 0).ToString() --> "0/0" instead of "Undefined", or
        //              new Rational(5).ToString()    --> "5/1" instead of "5"
        public override string ToString()
        {
            switch (Denominator)
            {
                case 0:
                    return "Undefined";
                case 1:
                    return Numerator.ToString();
            }
            return string.Format("{0}/{1}", Numerator, Denominator);
        }

        public int CompareTo(object other)
        {
            if (other == null) return 1;
            if (other is Rational) return CompareTo((Rational)other);
            throw new ArgumentException("Argument must be Rational");
        }

        public int CompareTo(Rational other)
        {
            if (IsUndefined)
            {
                // While IEEE decrees that floating point NaN's are not equal to each other,
                // I am not under any decree to adhere to that same specification for Rational.
                return other.IsUndefined ? 0 : -1;
            }
            if (other.IsUndefined) return 1;
            return this.ToDouble().CompareTo(other.ToDouble());
        }

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

        public override bool Equals(object other)
        {
            if (other == null) return false;
            if (other is Rational) return Equals((Rational)other);
            throw new ArgumentException("Argument must be Rational");
        }

        // Mofified code that was stolen from:
        // http://www.dotnetframework.org/default.aspx/4@0/4@0/DEVDIV_TFS/Dev10/Releases/RTMRel/ndp/clr/src/BCL/System/Double@cs/1305376/Double@cs
        // The hashcode for a double is the absolute value of the integer representation of that double.
        [System.Security.SecuritySafeCritical]  // auto-generated
        public unsafe override int GetHashCode()
        {
            if (Numerator == 0)
            {
                // Ensure that 0 and -0 have the same hash code
                return 0;
            }
            double d = ToDouble();
            long value = *(long*)(&d);
            return unchecked((int)value) ^ ((int)(value >> 32));
        }

        public static bool operator ==(Rational rat1, Rational rat2)
        {
            return rat1.Equals(rat2);
        }

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

        public static Rational operator +(Rational rat1, Rational rat2)
        {
            if (rat1.IsUndefined || rat2.IsUndefined)
            {
                return Undefined;
            }
            return new Rational
            {
                Numerator = rat1.Numerator * rat2.Denominator + rat1.Denominator * rat2.Numerator,
                Denominator = rat1.Denominator * rat2.Denominator
            }.Simplify();
        }

        public static Rational operator -(Rational rat1, Rational rat2)
        {
            if (rat1.IsUndefined || rat2.IsUndefined)
            {
                return Undefined;
            }
            return new Rational
            {
                Numerator = rat1.Numerator * rat2.Denominator - rat1.Denominator * rat2.Numerator,
                Denominator = rat1.Denominator * rat2.Denominator
            }.Simplify();
        }

        public static Rational operator *(Rational rat1, Rational rat2)
        {
            if (rat1.IsUndefined || rat2.IsUndefined)
            {
                return Undefined;
            }
            return new Rational
            {
                Numerator = rat1.Numerator * rat2.Numerator,
                Denominator = rat1.Denominator * rat2.Denominator
            }.Simplify();
        }

        public static Rational operator /(Rational rat1, Rational rat2)
        {
            if (rat1.IsUndefined || rat2.IsUndefined)
            {
                return Undefined;
            }
            return new Rational
            {
                Numerator = rat1.Numerator * rat2.Denominator,
                Denominator = rat1.Denominator * rat2.Numerator
            }.Simplify();
        }

        // The simplified Denominator will always be >= 0 for any Rational.
        // For a Rational to be negative, the simplified Numerator will be negative.
        // Thus a Rational(3, -4) would simplify to Rational(-3, 4).
        private Rational Simplify()
        {
            // These corner cases are very quick checks that means slightly longer code.
            // Yet I feel their explicit handling makes their logic more clear to future maintenance.
            // More importantly, it bypasses modulus and division when its not absolutely needed.
            if (IsUndefined) 
            {
                Numerator = 0;
                return this;
            }
            if (Numerator == 0)
            {
                Denominator = 1;
                return this;
            }
            if (IsInteger)   
            {
                return this;
            }
            if (Numerator == Denominator)
            {
                Numerator = 1;
                Denominator = 1;
                return this;
            }
            if (Denominator < 0)
            {
                // One special corner case when unsimplified Denominator is < 0 and Numerator equals int.MinValue.
                if (Numerator == int.MinValue)
                {
                    return ReduceOrThrow();
                }
                // Simpler and faster than mutiplying by -1
                Numerator = -Numerator;
                Denominator = -Denominator;
            }
            // We only perform modulus and division if we absolutely must.
            Reduce();
            return this;
        }

        private void Reduce()
        {
            var greatestCommonDivisor = GreatestCommonDivisor(Numerator, Denominator);
            Numerator /= greatestCommonDivisor;
            Denominator /= greatestCommonDivisor;
        }

        // Very special one off case: only called when unsimplified Numerater equals int.MinValue and Denominator is negative.
        // Some combinations produce a valid Rational, such as Rational(int.MinValue, int.MinValue), equivalent to Rational(1).
        // Others are not valid, such as Rational(int.MinValue, -1) because the Numerator would need to be (int.MaxValue + 1).
        private Rational ReduceOrThrow()
        {
            try
            {
                Reduce();
                return this;
            }
            catch
            {
                throw new ArgumentException(string.Format("Invalid Rational(int.MinValue, {0})", Denominator));
            }
        }

        public bool IsUndefined { get { return (Denominator == 0); } }

        public bool IsInteger { get { return (Denominator == 1); } }

        public double ToDouble()
        {
            if (IsUndefined) return double.NaN;
            return (double)Numerator / (double)Denominator;
        }

        // http://en.wikipedia.org/wiki/Euclidean_algorithm
        private static int GreatestCommonDivisor(int a, int b)
        {
            return (b == 0) ? a : GreatestCommonDivisor(b, a % b);
        }

    } //end struct

} //end namespace

Use of Negatives:

The sign of a Rational is determined by the Numerator. Thus a new Rational(3, -4) or Parse(“3/-4”) would both return Rational(-3, 4).

Undefined:

There are corner cases where the integer inputs do not return a valid Rational. This would only happen if the Denominator is negative and the Numerator equals int.MinValue. E.g. new Rational(int.MinValue, -2) returns a valid Rational but new Rational(int.MinValue, -1) would not.

Convenient Fields and Properties:

Like other numbers, Rational has a MinValue and MaxValue. Other convenient fields are Epsilon, Undefined, Zero, One, and MinusOne. Some convenient properties are IsUndefined and IsInteger.

Constructor Validation:

I imagine the biggest controversy is that I allow the 2 parameter constructor to throw an exception on invalid inputs. I’m aware of the argument that this is bad practice. Sure I could replace this constructor with a static Create method, the net effect is the same: anytime you create a new Rational it could possibly throw. So it’s wrong kill your neighbors but perfectly acceptable to hire someone else to do it?

I seriously debated the issue but ultimately decided to let the constructor throw. This keeps the use of Rational similar to other numbers, including Decimal, which also can throw during construction (example: new Decimal(double.NaN)).

\$\endgroup\$
  • 1
    \$\begingroup\$ You might want to use BigIntegers since nominator/denominator have the tendency to grow quickly. \$\endgroup\$ – CodesInChaos Mar 18 '15 at 18:20
  • \$\begingroup\$ Version 2 Link \$\endgroup\$ – Rick Davin Mar 18 '15 at 22:10
6
\$\begingroup\$

I like it very much (maybe other reviewers will disagree though).

A few things tickle a bit.

System namespace is not yours

I wouldn't put anything in the System namespace, whatever the reason is. That namespace belongs to the framework, and as much as your struct looks like it should be part of that framework, it isn't. And the day Microsoft ships a System.Rational, you have a clash.

this

The keyword this is inconsistently being used as a qualifier - sometimes it's there, sometimes it isn't. I'd just remove it, it's perfectly redundant.

ToString

The ToString implementation is switching on a non-enum value, and that switch block doesn't have a default case:

    public override string ToString()
    {
        switch (Denominator)
        {
            case 0:
                return "Undefined";
            case 1:
                return Numerator.ToString();
        }
        return string.Format("{0}/{1}", Numerator, Denominator);
    }

I'd live with the non-enum switch in the name of premature optimisation (does an if block really make a difference?), but move the return string.Format part into it.

Double-dip

In several places you're doing this:

return new Rational
{
    Numerator = /*expression*/,
    Denominator = /*expression*/
}.Simplify();

That's actually calling the default constructor (a 0/0 / Undefined instance) and accessing the private setters from outside that instance, which is violating the type's immutability and, some would argue, encapsulation. And then Simplify() returns yet another instance.

I don't like having public int SomeProperty { get; private set; } auto-properties in an immutable type, exactly for that reason. In my mind, a public property with a private setter should be 100% equivalent to this:

private readonly int _numerator;
public int Numerator { get { return _numerator; } }

But that would blow up your code with the above, because you're accessing the private setter.

Why not just do this instead?

return new Rational([expression], [expression]);

The constructor is calling Simplify anyway!

Immutable?

Wait a sec... is that struct really immutable?

private void Reduce()
{
    var greatestCommonDivisor = GreatestCommonDivisor(Numerator, Denominator);
    Numerator /= greatestCommonDivisor;
    Denominator /= greatestCommonDivisor;
}

Shouldn't that be private Rational Reduce(), and returning a new instance? You're dealing with a struct here - the two values ought to be considered as a single unit. I'm not sure how much of a violation that is, because the method is private, but it doesn't feel right that a struct internally mutates itself.

\$\endgroup\$
  • \$\begingroup\$ Oooh, I mixed up Simplify and Reduce ...will revisit this answer \$\endgroup\$ – Mathieu Guindon Mar 18 '15 at 17:22
  • \$\begingroup\$ Expect multiple comments. Tackling the short, easy ones that you recommend: System namespace – very valid and noted; this – also noted. I usually only use this when assigning properties (e.g. this.Value = value; ). I know C# is case-sensitive but if someone converted this to VB.NET it would not be happy. \$\endgroup\$ – Rick Davin Mar 18 '15 at 20:53
  • \$\begingroup\$ But... nobody converting C# to VB.NET should be happy ;) </semi-sarcasm> \$\endgroup\$ – Mathieu Guindon Mar 18 '15 at 20:54
  • 1
    \$\begingroup\$ Double Dipping – great catch. The code I copied from aush in the referenced link did not have a constructor of (int, int). He only used Parse() and TryParse(). With my own constructor, Simplify can be void instead of returning Rational. And everything will funnel through the constructor, producing cleaner code. \$\endgroup\$ – Rick Davin Mar 18 '15 at 20:56
  • 1
    \$\begingroup\$ RE: ToString. Will make an if-else check because it reads better. if (IsUndefined) is immediately more clear than case 0. \$\endgroup\$ – Rick Davin Mar 18 '15 at 21:29
3
\$\begingroup\$

In your ToString() method, you have three options, and you check two of them with a switch statement, and put the default outside the switch statement. switch statements have a built-in method for this situation - the default case:

public override string ToString()
{
    switch (Denominator)
    {
        case 0:
            return "Undefined";
        case 1:
            return Numerator.ToString();
        default:
            return string.Format("{0}/{1}", Numerator, Denominator);
    }
}

Turns out @Mat's Mug posted his answer first, but I'd already written this, so it won't hurt to mention it again.

You do not always put braces around if blocks. While braces are not required, it is good practice to always use them:

public int CompareTo(object other)
{
    if (other == null) { return 1; }
    if (other is Rational) { return CompareTo((Rational)other); }
    throw new ArgumentException("Argument must be Rational");
}

I didn't notice this, but @Mat's Mug is correct that you should never put anything in the System namespace. Put your programs in your own namespaces and using them as needed. This will also make it more obvious that you have to include your own files in the project rather than calling the .NET framework for this class.

\$\endgroup\$
  • \$\begingroup\$ Thanks for taking time to review and comment. I will address specific issues under Mat's answer. \$\endgroup\$ – Rick Davin Mar 18 '15 at 20:47
2
\$\begingroup\$

My two cents:

The method GreatestCommonDivisor will fail when a is zero.

    private static int GreatestCommonDivisor(int a, int b)
    {
        return (b == 0) ? a : GreatestCommonDivisor(b, a % b);
    }

When b is zero it will make the following code fail since it cannot divide by zero.

    private void Reduce()
    {
        var greatestCommonDivisor = GreatestCommonDivisor(Numerator, Denominator);
        Numerator /= greatestCommonDivisor;
        Denominator /= greatestCommonDivisor;
    }

Furthermore: the result of Simplify is not used in the constructor.

    public Rational(int numerator, int denominator = 1) : this()
    {
        this.Numerator = numerator;
        this.Denominator = denominator;
        // Comments...
        Simplify();
    }

I would expect it to be more like.

    public Rational(int numerator, int denominator = 1) : this()
    {
        this.Numerator = numerator;
        this.Denominator = denominator;
        // Comments...
        this = Simplify();
    }

However, this is made redundant because of the Reduce method, which just alters the values (see the last part of Mat's mug's post).

\$\endgroup\$
  • \$\begingroup\$ In light of @Mat's suggestions, I have other ideas on cleaning up Simplify, but the GCD is not a problem as it is only called by Reduce, and Reduce will not be called if Numerator or Denominator is 0. After that, the math all works out. Just ask Euclid. \$\endgroup\$ – Rick Davin Mar 18 '15 at 20:45
  • \$\begingroup\$ I think you should not trust on the methods who call a certain method, but rather on the method itself. If I call a framework function I want it to throw an exception when my input is invalid. Pre-checking my input values will be more of a 'bonus'. Try googling "Separation of concerns". \$\endgroup\$ – Mixxiphoid Mar 18 '15 at 21:19
  • \$\begingroup\$ Simplify, Reduce, and GCD are all private methods. If they were public, I would agree with you completely. \$\endgroup\$ – Rick Davin Mar 18 '15 at 21:31
  • \$\begingroup\$ Why should the content of a method differ when it is public? It should still do its job. Imagine that over a year you get back to this code and decide to enhance it. You are more likely to run into errors because you gave your code a manual on when to call it and when not, and it is very likely you don't remember that you cannot call these methods with certain values. If you cannot call a method with a certain value, the method should check for it himself and either solve it or throw an exception. \$\endgroup\$ – Mixxiphoid Mar 19 '15 at 5:55
1
\$\begingroup\$

I would suggest using an immutable class rather than a structure or, if you'd like something whose default value is Rational.Undefined rather than null, use a structure which wraps a reference to an immutable class object (and say that it's undefined if the reference is null).

Although this will entail some object-creation overhead when performing math on rational numbers, it will allow the code to avoid having to call Simplify after every operation. Suppose, for example, that one wants to add together the fractions (1/12)+(1/12)+(1/12)+(1/12) and output the result. Although it will be necessary to simplify the result before it can be displayed, simplifying the partial sums will be not only useless but counterproductive. Since all the denominators match, adding all the above numbers should require three additions and zero multiplications or divisions to yield 4/12. If the first sum is simplified to 1/6, it will have to be converted back to 2/12 before the next addition. If that's simplified 1/4, it will have to be converted back to 3/12 before the last addition. A lot of extra work.

I would suggest using an externally-immutable class with fields for "originalNumerator", "originalDenominator", "reducedNumerator", and "reducedDenominator"; the latter two would be initially zero, but could be lazily computed from the first two when required. I do not recommend overwriting the original numerator and denominator, since immutable classes are generally expected to be thread-safe; if the object had held 3/12 before simplify was called, and another thread examined it at that moment, it might erroneously see 3/4 or 1/12 depending upon whether the numerator or denominator was updated first. Having separate fields for the reduced value would mean that if a thread which sees either field as zero (when originalNumerator and originalDenominator aren't) calls simplify, then two threads which examine the same non-reduced value might call simplify simutaneously and end up doing redundant work, but everything would still behave correctly.

An advantage of using a class object over a structure is that if repeatedly performs operations on a non-reduced structure, the code performing each operation would likely receive a copy of the non-reduced structure, reduce it, act upon it, and then discard the reduced copy. By contrast, if each operation is performed on a class object, the first operation would perform the reduction and subsequent operations would then be able to use the reduced form.

\$\endgroup\$
  • 1
    \$\begingroup\$ These are very intriguing ideas. But as I think a Rational should be used like other numbers, which themselves are struct, I am inclined to keep this as struct. And I prefer Undefined over null. Thanks again. Very valid points. \$\endgroup\$ – Rick Davin Mar 18 '15 at 20:46
  • \$\begingroup\$ @RickDavin: If you want to use a struct, I'd suggest a struct which holds a reference to an object of a private RationalObject type. Once such an object is created, the number encapsulated thereby should never change (though as noted the reducedNumerator and reducedDenominator may be lazily comptued). From a client-code perspective, a structure holding such an object would be indistinguishable from one which held values directly except that after one structure holding to a RationalObject simplfied it, all structures holding a reference to it would benefit. \$\endgroup\$ – supercat Mar 18 '15 at 22:14
  • \$\begingroup\$ For something that I have no practical need, I would insist upon a struct. I've thought of having a Reducer class that transforms the inputs, along with Mat's idea that the struct backing fields should be readonly. You've given good ideas to chew on. Thanks. \$\endgroup\$ – Rick Davin Mar 20 '15 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.