14
\$\begingroup\$

I implemented most of the suggestions from Version 1. Thanks to all who took time to review and offer really good comments.

namespace NotSystemAndOthersThingsThatIHaveNoPracticalUseFor
{
    // This is Version 2.
    public struct Rational : IComparable, IComparable<Rational>, IEquatable<Rational>
    {
        // Retained from Version 1.
        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()
        {
            Numerator = numerator;
            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;
        }

        // Ver 2 Change: uses if's instead of switch(Denominator).  Should be easier for Sam The Maintainer.
        //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()
        {
            if (IsUndefined) { return "Undefined"; }
            if (IsInteger) { 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 ToDouble().CompareTo(other.ToDouble());
        }

        public bool Equals(Rational other)
        {
            if (IsUndefined) { return other.IsUndefined; }
            return (Numerator == other.Numerator) && (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);
        }

        // Version 2 Change for operators { +, -, *, / } :
        // Removed goofy call to Simplify() and rely upon constructor.
        // I use local variable n and d for better readability for Sam the Maintainer,
        // who's failing eyesight may miss a comma here and there.

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

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

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

        public static Rational operator /(Rational rat1, Rational rat2)
        {
            if (rat1.IsUndefined || rat2.IsUndefined)
            {
                return Undefined;
            }
            // fixed math error from Version 1
            var n = rat1.Numerator * rat2.Denominator;
            var d = rat1.Denominator * rat2.Numerator;
            return new Rational(n, d);
        }

        // Ver 2 Change: now void - no longer returns Rational.
        // 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 void 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;
            }
            if (Numerator == 0)
            {
                Denominator = 1;
                return;
            }
            if (IsInteger)
            {
                return;
            }
            if (Numerator == Denominator)
            {
                Numerator = 1;
                Denominator = 1;
                return;
            }
            if (Denominator < 0)
            {
                // One special corner case when unsimplified Denominator is < 0 and Numerator equals int.MinValue.
                if (Numerator == int.MinValue)
                {
                    ReduceOrThrow();
                    return;
                }
                // Simpler and faster than mutiplying by -1
                Numerator = -Numerator;
                Denominator = -Denominator;
            }
            // We only perform modulus and division if we absolutely must.
            Reduce();
        }

        private void Reduce()
        {
            // Reduce() is never called if Numerator or Denominator equals 0.
            var greatestCommonDivisor = GreatestCommonDivisor(Numerator, Denominator);
            Numerator /= greatestCommonDivisor;
            Denominator /= greatestCommonDivisor;
        }

        // Ver 2 Change: now void - no longer returns Rational.
        // 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 void ReduceOrThrow()
        {
            try
            {
                Reduce();
            }
            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

Double-dipping, Simplify(), and overuse of this

Simplify() was simplified to be void, as was ReduceOrThrow(), instead of returning Rational. More importantly, the double-dipped references to Simplify() inside the operator code was removed. Using the constructor instead of Simpify() cleaned the logic up nicely. These changes removed about 85% of my use of this, and I cleaned the remaining stragglers.

ToString()

No longer uses switch(Denominator). The if logic looks much cleaner now. Though it is in the complete code block above, it received so many comments that the new logic deserves repeating here:

public override string ToString()
{
    if (IsUndefined) { return "Undefined"; }
    if (IsInteger) { return Numerator.ToString(); }
    return string.Format("{0}/{1}", Numerator, Denominator);
}

I think the new logic is far more understandable to Sam the Maintainer.

Other, etc

I fixed a math error in my division operator.

Despite Mat’s comments, I kept:

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

If a single line if is not wrapped in braces, then it’s a typo. I tried to add them where needed, but this day has been long for real work.

\$\endgroup\$
  • \$\begingroup\$ Version 1 may be found at link \$\endgroup\$ – Rick Davin Mar 18 '15 at 22:10
  • 5
    \$\begingroup\$ Rational r = new Rational(2000000000, 2000000001); Console.WriteLine(r + r); Prints 139397120/-389294899 \$\endgroup\$ – Dennis_E Mar 18 '15 at 22:57
  • \$\begingroup\$ @Dennis_E Congratulations, you overflowed \$\endgroup\$ – Cole Johnson Mar 19 '15 at 13:09
  • 2
    \$\begingroup\$ @ColeJohnson That's what I was trying to hint at: he needs to decide how to handle overflow. \$\endgroup\$ – Dennis_E Mar 19 '15 at 13:29
  • \$\begingroup\$ @Dennis_E I am aware of the overflow and definitely agree that it should be addressed, along with the immutability issue. \$\endgroup\$ – Rick Davin Mar 20 '15 at 12:32
4
\$\begingroup\$

CompareTo shouldn't convert both arguments to doubles; that loses precision, and negates one major benefit of using rationals at all. Rather, to compare a/b with c/d, where b and d are both positive, you should compare a*d with b*c. (Remember to do the multiplication and compare in a long context, to prevent overflow.)

Also, although I understand that it's a matter of opinion, I don't like that Rationals don't automatically simplify themselves. It means that 1/2 won't be Equal() to 2/4 or -1/-2, and it means that adding up 32 1/2s will cause overflow.

Finally, this was mentioned before, but you should really strongly consider making this struct immutable, with no setters on the numerator/denominator. Setting only one of those is a really unusual thing to do, like changing only the second digit of an integer. Setting only one at a time makes it impractical to put checks in the numerator/denominator setter functions. And idiomatically, mathematical value types like this are usually implemented as immutable.

\$\endgroup\$
  • \$\begingroup\$ Not that I must pick an answer, and no one answer is fully correct. But yours brings up points that I have thought about and feel should be addressed (if I were to resume coding this in the next 4-6 months). \$\endgroup\$ – Rick Davin Mar 20 '15 at 12:31
  • \$\begingroup\$ " I don't like that Rationals don't automatically simplify themselves" But they do? As long as you use the constructor, anyway, which is the only way external code can create a Rational other than 0/0 \$\endgroup\$ – Ben Aaronson Mar 20 '15 at 13:15
  • \$\begingroup\$ @BenAaronson The sum or product of two simplified Rationals will not necessarily be simplified itself. \$\endgroup\$ – Sneftel Mar 20 '15 at 14:42
  • \$\begingroup\$ @Sneftel Why not? It uses the constructor \$\endgroup\$ – Ben Aaronson Mar 20 '15 at 16:15
  • \$\begingroup\$ @BenAaronson You're right-- I don't know how I missed that flow of control. \$\endgroup\$ – Sneftel Mar 20 '15 at 16:35
14
\$\begingroup\$
namespace NotSystemAndOthersThingsThatIHaveNoPracticalUseFor

I couldn't possibly imagine a worse namespace.

Why not use something both simpler and more descriptive?

namespace RationalMath
\$\endgroup\$
  • 4
    \$\begingroup\$ While I realize OP is probably just creating a placeholder, I also felt the need to mention this, so +1. \$\endgroup\$ – DLeh Mar 19 '15 at 18:50
12
\$\begingroup\$

Is there any particular reason for TryCreate? There doesn't seem to be much more reason for this to have a static constructor than any other class (or struct!). Since it doesn't use any non-public fields, anyone who really finds themselves needing this could easily create it themselves, throwing it in seems like a (minor) YAGNI violation


TryParse internally calls Parse. It'd probably be better to do it the other way around, avoiding using exceptions for non-exceptional situations. Throwing and catching exceptions for such a simple operation can actually have a non-negligible performance impact, though I don't know how slow it is compared to the normal speed of parsing.


var n = (rat1.Numerator * rat2.Denominator) + (rat1.Denominator * rat2.Numerator);
var d = rat1.Denominator * rat2.Denominator;
return new Rational(n, d);

This is certainly the neatest way of doing this, but falls due to overflow issues if my two rationals have large numerators and denominators.


Couldn't some operations be defined by their inverses? For example, A - B = A + (-B). The cost of this is extremely small because you can create -B by setting the fields directly as you do in the constants


You might consider having three cases for rationals in the form a/0: PositiveInfinity, Undefined and NegativeInfinity, corresponding to a > 0, a = 0 and a < 0 respectively. This is what, e.g. Double does (see the source )


GetHashCode() has:

[System.Security.SecuritySafeCritical]  // auto-generated

Presumably copied from the Double version, but this shouldn't be here, especially as that comment is a lie!

More generally, this implementation doesn't really make any sense. Why convert to a double then manually re-implement Double's version? Why not just return ToDouble().GetHashCode();?

A simpler way of getting a hash code for situations like this would be return Tuple.Create(Numerator,Denominator).GetHashCode(); or return new {Numerator, Denominator}.GetHashCode(); However, in this case I think it's not premature to assume that performance may be important for this method, so it'd be worth doing a quick comparison of the performance of all three methods. I suspect yours may be faster.

There are yet more possibilities, probably even faster than your version. See this SO question, for example.


According to MSDN:

Implementations of Equals must not throw exceptions; they should always return a value.

So if you pass in an object of the wrong type, Equals should return false rather than throwing.

\$\endgroup\$
8
\$\begingroup\$
// There is a special case where Simplify() could throw an exception:
//...

Great documentation, but what is this special case? You've gone to great lengths to explain what you decided and why, but never actually state under what conditions the constructor will throw an error.

// This is only called by Parse.

Comments like this tend to lie sooner or later. What happens when you find a need to use it else where later and forget to remove the comment? The IDE will tell you where all a method is called if you ask it. I would remove this unless what you really meant was

// This should only called by Parse.

Since it appears I'm reviewing your comments, I'll just leave you with one last note. This is the kind of library code that could really benefit from good XML doc comments.

For example, your CompareTo implementation doesn't conform to the standards (per your comments), so it would be beautiful to see the expected return value in the IDE as I'm using your library.

\$\endgroup\$
5
\$\begingroup\$

Your numerator and denominator should be BigInteger (MSDN); otherwise you get overflow situations like this (prints 139397120/-389294899):

Rational r = new Rational(2000000000, 2000000001);
Console.WriteLine(r + r);

So, change your instance variable lines for Numerator and Denominator to:

public BigInteger Numerator { get; private set; }
public BigInteger Denominator { get; private set; }
\$\endgroup\$
  • \$\begingroup\$ A bigger issue I think is that intermediate computations should be able to use larger values than those fed into the calculation (e.g. if the type uses Int32, then calculations should use Int64). I don't have a problem with a type faulting when a calculation yields a value it can't accurately represent, but it's ugly to fail on a computation which yields a fraction that could be reduced to fit. \$\endgroup\$ – supercat Mar 20 '15 at 5:39
  • \$\begingroup\$ @supercat That's why I recommended BigInteger as well \$\endgroup\$ – Cole Johnson Mar 20 '15 at 14:00
  • 1
    \$\begingroup\$ BigInteger has a lot of overhead. Casting to Int64 during calculations and then back to Int32 after simplify would significantly increase the type's useful numeric range compared with using Int32 everywhere, with much less added cost. \$\endgroup\$ – supercat Mar 20 '15 at 14:55
  • \$\begingroup\$ @supercat Yes, using long for intermediate storage would work because Int32.MaxValue * Int32.MaxValue < Int64.MaxValue (proof). I am well aware of that. When I recommended BigInteger, I meant for storage. As in: set the types of numerator and denominator to BigInteger. That way, you'll have unlimited precision (albeit bound by memory). \$\endgroup\$ – Cole Johnson Mar 20 '15 at 16:02
  • \$\begingroup\$ Much of the value of rational types arises from situations where values stay fairly small. I'm not sure how often it's particularly useful to perform computations with fractions whose numerator and denominator get to be dozens or hundreds of digits long. \$\endgroup\$ – supercat Mar 20 '15 at 16:32
3
\$\begingroup\$

There are several things I would change, based on my previous attempts at implementing rational numbers. I implemented them in C++ and never once wrote a piece of C# so my advice may be wrong:

  • First of all, I would probably make Rational a generic class so that you can use int, long or BigInteger as the underlying type, depending on your needs or on those of the people who will use your class. It seems that generic don't mix well with every part of the language though so there might be shortcomings.

  • I would add specific overloads to operators so that your class can interact directly with instances of the underlying type (int in your case), providing shortcuts and avoiding to always recreate more Rational instances even when you don't have to.

  • Some operations between rational numbers and integers do not require any simplification at all since they can't denormalize the fraction (actually, it would be great if anybody could find me a formal proof). It is the case for example of the rational-integer addition:

    public static Rational operator +(Rational rat, int other)
    {
        return new Rational(
            rat.Numerator + other * rat.Denominator,
            rat.Denominator
        );
    }
    
  • You could also tweak some of these algorithms so that your operators always simplify the result and avoid overflows when possible:

    public static Rational operator *(Rational rat, int other)
    {
        var divisor = GreatestCommonDivisor(rat.Denominator, other);
        other /= divisor;
        return new Rational(
            rat.Numerator * other,
            rat.Denominator / divisor
        );
    }
    
\$\endgroup\$
  • 1
    \$\begingroup\$ While there might be uses for an IFraction<T> interface which can report a numerator and denominator as type T, the code required to work with fractions stored as Int32 will be significantly different from that required to work with fractions stored as Int64 or BigInteger. \$\endgroup\$ – supercat Mar 20 '15 at 16:35
  • \$\begingroup\$ @supercat "Significantly"? How so? Note that this isn't sarcastic. I hardly know C# and would be interested in knowing what would differ. \$\endgroup\$ – Morwenn Mar 20 '15 at 16:41
  • \$\begingroup\$ For the version with fields of type Int32, code could cast to Int64 when performing intermediate computations and then reduce results afterward. For the version with fields of type Int64, code would need to be able to determine whether an Int64 would have any factors in common with a sum of products that are too big to fit in that type without having an efficient larger type at its disposal. \$\endgroup\$ – supercat Mar 20 '15 at 17:10
  • \$\begingroup\$ @supercat Using algorithms such as the last one in my post (you can find equivalents for every basic operation looking at the source code of Boost.Rational), it should be possible to not overflow an Int32 if the result of the operation can be represented as an Int32. Doesn't this allow for a generic representation? \$\endgroup\$ – Morwenn Mar 20 '15 at 17:17
  • \$\begingroup\$ If one can easily find workable versions for all operations, that would help reduce the differences. There's still a rather annoying problem, though, which accidentally edited out of my comment, which is the generic mechanism in .NET requires that the code for all of the types generated by a generic type family must have the same CIL representation, but arithmetic operators require different CIL instructions for different data types. One might be able to have three source files--one for each type--which were almost identical except for a few lines at the top, but unless one uses... \$\endgroup\$ – supercat Mar 20 '15 at 17:36
1
\$\begingroup\$

Is is unusual to throw an exception in equals. This might be useful here, since it sounds unlikely that we check for equality with a different class (potential bug) - but this is just speculation.

Either way, exception messages should terminate with a .-dot/full stop, this is missing.

\$\endgroup\$

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.