4
\$\begingroup\$

I've been recently working on a custom rational number implementation. Due to not very interesting reasons, using this implementation is not an option.

I'd appreciate comments of anyone who has the time to review the code. The posted code is free to use, so you can make good use of it should you want/need to.

The implementation is basically finished except the Parse and TryParse methods which I'm still working on.

I'm particularly interested in the FromDouble and TryFromDouble methods which I think are working relatively well but any suggestions, improvements or discovery of any, so far, undetected bugs are very welcomed.

using System;
using System.Diagnostics;
using System.Globalization;
using System.Numerics;

namespace MathSuite.Core.Numeric
{
    [Serializable]
    public struct Rational : IFormattable, IEquatable<Rational>, IComparable<Rational>, IComparable
    {
        #region Static fields
        const string positiveInfinityLiteral = "Infinity";
        const string negativeInfinityLiteral = "-Infinity";
        const string naNLiteral = "NaN";
        const int fromDoubleMaxIterations = 25;

        static readonly Rational one = new Rational(1);
        static readonly Rational zero = new Rational(0);
        static readonly Rational naN = new Rational(0, 0, true);
        static readonly Rational positiveInfinity = new Rational(1, 0, true);
        static readonly Rational negativeInfinity = new Rational(-1, 0, true);
        #endregion

        #region Instance fields
        readonly BigInteger numerator, denominator;
        readonly bool explicitConstructorCalled, isDefinitelyIrreducible;
        #endregion

        #region Constructors
        [DebuggerStepThrough]
        public Rational(BigInteger numerator)
            : this(numerator, 1, true) { }

        [DebuggerStepThrough]
        public Rational(BigInteger numerator, BigInteger denominator)
            : this(numerator, denominator, false) { }

        [DebuggerStepThrough]
        private Rational(Rational numerator, Rational denominator)
            : this(numerator.numerator * denominator.Denominator, numerator.Denominator * denominator.numerator, false) { }

        private Rational(BigInteger numerator, BigInteger denominator, bool isIrreducible)
        {
            if (denominator < 0) //normalize to positive denominator
            {
                this.denominator = -denominator;
                this.numerator = -numerator;
            }
            else
            {
                this.numerator = numerator;
                this.denominator = denominator;
            }

            this.explicitConstructorCalled = true;
            this.isDefinitelyIrreducible = isIrreducible;
        }
        #endregion

        #region Instance properties
        public BigInteger Denominator { get { return explicitConstructorCalled ? denominator : 1; } } //We want default value to be zero, not NaN.

        public Rational FractionalPart
        {
            get
            {
                if (Denominator != 0)
                {
                    if (IsProper(this))
                        return new Rational(numerator % Denominator, Denominator);

                    return new Rational(BigInteger.Abs(numerator % Denominator), Denominator);
                }

                if (numerator == 0)
                    return naN;

                if (numerator > 0)
                    return positiveInfinity;

                return negativeInfinity;
            }
        }

        public Rational IntegerPart
        {
            get
            {
                if (Denominator != 0)
                    return (BigInteger)this;

                if (numerator == 0)
                    return naN;

                if (numerator > 0)
                    return positiveInfinity;

                return negativeInfinity;
            }
        }

        public BigInteger Numerator { get { return numerator; } }

        public Rational Sign { get { return numerator.Sign; } }
        #endregion

        #region Instance methods
        public int CompareTo(Rational other)
        {
            //Even though neither infinities nor NaNs are equal to themselves, for 
            //comparison's sake it makes sense to return 0 when comparing PositiveInfinities
            //or NaNs, etc. The only other option would be to throw an exception...yuck.

            if (Rational.IsNaN(other))
                return Rational.IsNaN(this) ? 0 : 1;

            if (Rational.IsNaN(this))
                return Rational.IsNaN(other) ? 0 : -1;

            if (Rational.IsPositiveInfinity(this))
                return Rational.IsPositiveInfinity(other) ? 0 : 1;

            if (Rational.IsNegativeInfinity(this))
                return Rational.IsNegativeInfinity(other) ? 0 : -1;

            if (Rational.IsPositiveInfinity(other))
                return Rational.IsPositiveInfinity(this) ? 0 : -1;

            if (Rational.IsNegativeInfinity(other))
                return Rational.IsNegativeInfinity(this) ? 0 : 1;

            return (this.numerator * other.Denominator).CompareTo(this.Denominator * other.numerator);
        }

        public int CompareTo(object obj)
        {
            if (obj is Rational)
                return this.CompareTo((Rational)obj);

            if (obj == null)
                return 1;

            throw new ArgumentException("obj is not a RationalNumber.", "obj");
        }

        public bool Equals(Rational other)
        {
            if (this.Denominator == 0 || other.Denominator == 0) //By definition NaNs and infinities are not equal.
                return false;

            return this.numerator * other.Denominator == this.Denominator * other.numerator;
        }

        public override bool Equals(object obj)
        {
            if (obj is Rational)
                return this.Equals((Rational)obj);

            return false;
        }

        [DebuggerStepThrough]
        public override int GetHashCode()
        {
            if (isDefinitelyIrreducible)
            {
                unchecked
                {
                    return this.numerator.GetHashCode() ^ this.Denominator.GetHashCode();
                }
            }

            return Rational.GetReducedForm(this).GetHashCode();
        }

        [DebuggerStepThrough]
        public override string ToString()
        {
            return ToString(null, null);
        }

        [DebuggerStepThrough]
        public string ToString(string format)
        {
            return ToString(format, null);
        }

        [DebuggerStepThrough]
        public string ToString(IFormatProvider formatProvider)
        {
            return ToString(null, formatProvider);
        }

        public string ToString(string format, IFormatProvider formatProvider)
        {
            try
            {
                if (formatProvider is RationalFormatProvider)
                    return ((RationalFormatProvider)formatProvider).Format(format ?? "G", this, CultureInfo.CurrentCulture);

                var rationalFormatProvider = new RationalFormatProvider();
                return rationalFormatProvider.Format(format ?? "G", this, formatProvider ?? CultureInfo.CurrentCulture);
            }
            catch (FormatException e)
            {
                throw new FormatException(String.Format("The specified format string '{0}' is invalid.", format), e);
            }
        }
        #endregion

        #region Static properties
        public static bool IsInfinity(Rational rationalNumber)
        {
            return Rational.IsPositiveInfinity(rationalNumber) ||
                   Rational.IsNegativeInfinity(rationalNumber);
        }

        public static bool IsIrreducible(Rational rationalNumber)
        {
            if (rationalNumber.isDefinitelyIrreducible)
                return true;

            if (rationalNumber.Denominator == 1 ||
                (rationalNumber.Denominator == 0 && (rationalNumber.numerator == 1 || rationalNumber.numerator == -1 || rationalNumber.numerator == 0)) ||
                Tools.GreatestCommonDivisor(rationalNumber.numerator, rationalNumber.Denominator) == 1)
            {
                return true;
            }

            return false;
        }

        public static bool IsPositiveInfinity(Rational rationalNumber)
        {
            return rationalNumber.Denominator == 0 && rationalNumber.numerator > 0; //Can not check using rationalNumber == positiveInfinity because by definition
            //infinities are not equal.
        }

        public static bool IsProper(Rational rationalNumber)
        {
            return BigInteger.Abs(rationalNumber.IntegerPart.numerator) < 1;
        }

        public static bool IsNaN(Rational rationalNumber)
        {
            return rationalNumber.Denominator == 0 && rationalNumber.numerator == 0; //Can not check using rationalNumber == naN because by definition NaN are not equal.
        }

        public static bool IsNegativeInfinity(Rational rationalNumber)
        {
            return rationalNumber.Denominator == 0 && rationalNumber.numerator < 0; //Can not check using rationalNumber == negativeInfinity because by definition
            //infinities are not equal.
        }

        public static Rational One { get { return one; } }

        public static Rational PositiveInfinity { get { return positiveInfinity; } }

        public static Rational NaN { get { return naN; } }

        public static Rational NegativeInfinity { get { return negativeInfinity; } }

        public static Rational Zero { get { return zero; } }
        #endregion

        #region Static methods
        public static Rational Abs(Rational number)
        {
            return new Rational(BigInteger.Abs(number.numerator), number.Denominator);
        }

        public static Rational Add(Rational left, Rational right, bool reduceOutput = false)
        {
            return reduceOutput ? Rational.GetReducedForm(left + right) : left + right;
        }

        public static Rational Ceiling(Rational number)
        {
            if (number.FractionalPart == zero)
                return number.IntegerPart;

            if (number < zero)
                return number.IntegerPart;

            return number.IntegerPart + 1;
        }

        public static Rational Divide(Rational left, Rational right, bool reduceOutput = false)
        {
            return reduceOutput ? Rational.GetReducedForm(left / right) : left / right;
        }

        public static Rational Floor(Rational number)
        {
            if (number.FractionalPart == zero)
                return number.IntegerPart;

            if (number < zero)
                return number.IntegerPart - 1;

            return number.IntegerPart;
        }

        public static Rational FromDouble(double target, double precision)
        {
            Rational result;

            if (!TryFromDouble(target, precision, out result))
                throw new ArgumentException("Can not find a rational aproximation with the specified precision.", "precision");

            return result;
        }

        public static Rational GetReciprocal(Rational rationalNumber)
        {
            return new Rational(rationalNumber.Denominator, rationalNumber.numerator, rationalNumber.isDefinitelyIrreducible);
        }

        public static Rational GetReducedForm(Rational rationalNumber)
        {
            if (rationalNumber.isDefinitelyIrreducible)
            {
                return rationalNumber;
            }

            var greatesCommonDivisor = Tools.GreatestCommonDivisor(rationalNumber.numerator, rationalNumber.Denominator);
            return new Rational(rationalNumber.numerator / greatesCommonDivisor, rationalNumber.Denominator / greatesCommonDivisor, true);
        }

        public static Rational Max(Rational first, Rational second)
        {
            if (first >= second)
                return first;

            return second;
        }

        public static Rational Min(Rational first, Rational second)
        {
            if (first <= second)
                return first;

            return second;
        }

        public static Rational Multiply(Rational left, Rational right, bool reduceOutput = false)
        {
            return reduceOutput ? Rational.GetReducedForm(left * right) : left * right;
        }

        public static Rational Negate(Rational right, bool reduceOutput = false)
        {
            return reduceOutput ? Rational.GetReducedForm(-right) : -right;
        }

        public static Rational Pow(Rational r, int n, bool reduceOutput = false)
        {
            if (Rational.IsNaN(r))
            {
                return naN;
            }

            if (n > 0)
            {
                var result = new Rational(BigInteger.Pow(r.numerator, n), BigInteger.Pow(r.Denominator, n), false);
                return reduceOutput ? Rational.GetReducedForm(result) : result;
            }

            if (n < 0)
            {
                return Pow(GetReciprocal(r), -n, reduceOutput);
            }

            if (r == zero || Rational.IsInfinity(r))
            {
                return naN;
            }

            return one;
        }

        public static Rational Subtract(Rational left, Rational right, bool reduceOutput = false)
        {
            return reduceOutput ? Rational.GetReducedForm(left - right) : left - right;
        }

        public static double ToDouble(Rational rationalNumber)
        {
            return ((double)rationalNumber.numerator) / (double)rationalNumber.Denominator;
        }

        public static Rational Truncate(Rational number)
        {
            return number.IntegerPart;
        }

        public static bool TryFromDouble(double target, double precision, out Rational result)
        {
            //Continued fraction algorithm: http://en.wikipedia.org/wiki/Continued_fraction
            //Implemented recursively. Problem is figuring out when precision is met without unwinding each solution. Haven't figured out how to do that.
            //Current implementation computes rational number approximations for increasing algorithm depths until precision criteria is met, maximum depth is reached (fromDoubleMaxIterations)
            //or an OverflowException is thrown. Efficiency is probably improvable but this method will not be used in any performance critical code. No use in optimizing it unless there is
            //a good reason. Current implementation works reasonably well.

            result = zero;
            int steps = 0;

            while (Math.Abs(target - Rational.ToDouble(result)) > precision)
            {
                if (steps > fromDoubleMaxIterations)
                {
                    result = zero;
                    return false;
                }

                result = getNearestRationalNumber(target, 0, steps++);
            }

            return true;
        }

        private static Rational getNearestRationalNumber(double number, int currentStep, int maximumSteps)
        {
            var integerPart = (BigInteger)number;
            double fractionalPart = number - Math.Truncate(number);

            while (currentStep < maximumSteps && fractionalPart != 0)
            {
                return integerPart + new Rational(1, getNearestRationalNumber(1 / fractionalPart, ++currentStep, maximumSteps));
            }

            return new Rational(integerPart);
        }
        #endregion

        #region Operators
        public static explicit operator double(Rational rationalNumber) { return Rational.ToDouble(rationalNumber); }

        public static implicit operator Rational(BigInteger number) { return new Rational(number); }

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

        public static explicit operator BigInteger(Rational rationalNumber) { return rationalNumber.numerator / rationalNumber.Denominator; }

        public static bool operator ==(Rational left, Rational right) { return left.Equals(right); }

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

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

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

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

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

        public static Rational operator +(Rational right)
        {
            return right;
        }

        public static Rational operator -(Rational right)
        {
            return new Rational(-right.numerator, right.Denominator, right.isDefinitelyIrreducible);
        }

        public static Rational operator +(Rational left, Rational right)
        {
            if ((IsPositiveInfinity(left) && IsPositiveInfinity(right)) || //Otherwise the sum of two equally signed infinities would return NaN which is not correct.
                (IsNegativeInfinity(left) && IsNegativeInfinity(right)))
                return left;

            return new Rational(left.Numerator * right.Denominator + right.numerator * left.Denominator, left.Denominator * right.Denominator, false);
        }

        public static Rational operator -(Rational left, Rational right)
        {
            return left + (-right);
        }

        public static Rational operator *(Rational left, Rational right)
        {
            return new Rational(left.numerator * right.numerator, left.Denominator * right.Denominator, false);
        }

        public static Rational operator /(Rational left, Rational right)
        {
            if ((IsInfinity(left) && IsInfinity(right)) ||
                (left == zero && right == 0))
                return naN;

            return new Rational(left.numerator * right.Denominator, left.Denominator * right.numerator, false);
        }
        #endregion

        [DebuggerStepThrough]
        private class RationalFormatProvider : IFormatProvider, ICustomFormatter
        {
            public object GetFormat(Type formatType)
            {
                if (formatType == typeof(ICustomFormatter))
                    return this;

                return null;
            }

            public string Format(string format, object arg, IFormatProvider formatProvider)
            {
                var upperFormat = format != null ? format.ToUpperInvariant().TrimStart() : "G";

                if (!(arg is Rational))
                    return hanldeOtherFormats(format, arg, formatProvider);

                var rational = (Rational)arg;

                if (rational.Denominator == 0)
                {
                    if (rational.numerator == 0)
                    {
                        return naNLiteral;
                    }

                    if (rational.numerator > 0)
                    {
                        return positiveInfinityLiteral;
                    }

                    return negativeInfinityLiteral;
                }

                string innerFormat = format;

                if (upperFormat[0] == 'M')
                {
                    innerFormat = format.Replace('M', 'G');
                    var integerPart = rational.IntegerPart.Numerator;

                    if (integerPart != 0)
                    {
                        var fractionalPart = rational.FractionalPart;
                        return string.Format("{0} [{1}/{2}]", integerPart.ToString(innerFormat, formatProvider),
                            BigInteger.Abs(fractionalPart.numerator).ToString(innerFormat, formatProvider), fractionalPart.Denominator.ToString(innerFormat, formatProvider));
                    }
                }

                return string.Format("{0}/{1}", rational.numerator.ToString(innerFormat, formatProvider), rational.Denominator.ToString(innerFormat, formatProvider));
            }

            private string hanldeOtherFormats(string format, object arg, IFormatProvider formatProvider)
            {
                if (arg is IFormattable)
                    return ((IFormattable)arg).ToString(format, formatProvider);

                if (arg != null)
                    return arg.ToString();

                return String.Empty;
            }
        }
    }
}

And the relevant implementation of the auxiliary class Tools:

using System;
using System.Numerics;

namespace MathSuite.Core.Numeric
{
    internal static class Tools
    {
        public static BigInteger LeastCommonMultiple(BigInteger number1, BigInteger number2)
        {
            if (number1 == 0) return number2;
            if (number2 == 0) return number1;

            var positiveNumber2 = number2 < 0 ? BigInteger.Abs(number2) : number2;
            var positiveNumber1 = number1 < 0 ? BigInteger.Abs(number1) : number1;

            return positiveNumber1 / GreatestCommonDivisor(positiveNumber1, positiveNumber2) * positiveNumber2;
        }

        public static BigInteger GreatestCommonDivisor(BigInteger number1, BigInteger number2)
        {
            var positiveNumber2 = number2 < 0 ? BigInteger.Abs(number2) : number2;
            var positiveNumber1 = number1 < 0 ? BigInteger.Abs(number1) : number1;

            if (positiveNumber1 == positiveNumber2)
                return positiveNumber1;

            if (positiveNumber1 == 0)
                return positiveNumber2;

            if (positiveNumber2 == 0)
                return positiveNumber1;

            if ((~positiveNumber1 & 1) != 0)
            {
                if ((positiveNumber2 & 1) != 0)
                {
                    return GreatestCommonDivisor(positiveNumber1 >> 1, positiveNumber2);
                }
                else
                {
                    return GreatestCommonDivisor(positiveNumber1 >> 1, positiveNumber2 >> 1) << 1;
                }
            }

            if ((~positiveNumber2 & 1) != 0)
            {
                return GreatestCommonDivisor(positiveNumber1, positiveNumber2 >> 1);
            }

            if (positiveNumber1 > positiveNumber2)
            {
                return GreatestCommonDivisor((positiveNumber1 - positiveNumber2) >> 1, positiveNumber2);
            }

            return GreatestCommonDivisor((positiveNumber2 - positiveNumber1) >> 1, positiveNumber1);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ What exactly are you looking for? Any tips? Readability tips? Performance tips? Best practice tips? \$\endgroup\$ – Der Kommissar Jul 6 '15 at 19:20
3
\$\begingroup\$

Unchecked

There's no need for the unchecked context in GetHashCode. Bitwise operators never cause overflow, and as such checked/unchecked has no effect on them. The unchecked context only affects certain arithmetic operators.

https://msdn.microsoft.com/en-us/library/vstudio/6a71f45d(v=vs.100).aspx
https://msdn.microsoft.com/en-us/library/khy08726.aspx
https://msdn.microsoft.com/en-us/library/a569z7k8.aspx

Constants (Debatable)

Constants (const) are typically all uppercase with words separated by underscores. This is a best-practices rule more than anything.

Note: as stated in the comments, this goes against the .NET general naming conventions:

  1. DO NOT use underscores, hyphens, or any other nonalphanumeric characters.
  2. DO use PascalCasing for all public member, type, and namespace names consisting of multiple words.

This is obviously a personal choice, but I would always use the all-caps style, as this makes it more explicit. It also makes it more difficult to find constants with Intellisense and the like. The all-caps constants stand out immediately. Typically, people coming from a C, C++, Java or even PHP background like myself tend to stick to ALL_CAPS constants, as they are generally the standard for such languages. While I agree with a large amount of what the MSDN says about naming, this is one of the few points I disagree with. Again, this is a personal preference. Were I writing the code, the const fields would be CONST_FIELDS instead of ConstFields.

Visibility/Access Modifiers

Generally, it is best accepted to specify explicit visibility modifiers. Don't allow the private access modifier to be assumed. (Yes, I know, that adds more text and can make it hard to read. But it also makes it perfectly clear what the intention was.)

Readonly Fields/Properties

As RubberDuck said, there's no need to have properties for the readonly fields. It adds unnecessary clutter. Making the readonly fields public works just as well.

Consistency

Some of your if statements with one line to be executed have curly braces, some do not. I have removed them from all the ones that have them and were single-statement if's. This is more a consistency standpoint than anything.

TryFromDouble/FromDouble/GetNearestRationalNumber

You were most interested in the TryFromDouble and FromDouble methods, so here is my comment on them. The TryFromDouble method is the more important one, as FromDouble uses it, so I dove into it and also investigated the getNearestRationalNumber method.

In getNearestRationalNumber, you directly compare a double to 0. This is generally a bad practice, due to floating-point error. I would, instead, pick an Epsilon that you can use to compare it to. I.e. && fractionalPart < Epsilon. There is also no need for the while loop in that method, it would only execute once due to the early-return. You can change that to an if.

Tools Class

Lastly, I would make Tools public. You could also make those extension methods. (LeastCommonMultiple(this Biginteger number1, BigInteger number2) and use it as BigInteger number = 1; number.LeastCommonMultiple(2); et al.) This makes it easier to access.

RationalFormatProvider

You had a misspelling in RationalFormatProvider (hanldeOtherFormats), I fixed this as well.

Otherwise, it's a nicely put-together implementation. I like the simplicity of it and the consistency you did keep.

Rational class:

[Serializable]
public struct Rational : IFormattable, IEquatable<Rational>, IComparable<Rational>, IComparable
{
    #region Static fields
    private const string POSITIVE_INFINITY_LITERAL = "Infinity";
    private const string NEGATIVE_INFINITY_LITERAL = "-Infinity";
    private const string NAN_LITERAL = "NaN";
    private const int FROM_DOUBLE_MAX_ITERATIONS = 25;

    public static readonly Rational One = new Rational(1);
    public static readonly Rational Zero = new Rational(0);
    public static readonly Rational NaN = new Rational(0, 0, true);
    public static readonly Rational PositiveInfinity = new Rational(1, 0, true);
    public static readonly Rational NegativeInfinity = new Rational(-1, 0, true);
    #endregion

    #region Instance fields
    private readonly BigInteger numerator, denominator;
    private readonly bool explicitConstructorCalled, isDefinitelyIrreducible;
    #endregion

    #region Constructors
    [DebuggerStepThrough]
    public Rational(BigInteger numerator)
        : this(numerator, 1, true)
    { }

    [DebuggerStepThrough]
    public Rational(BigInteger numerator, BigInteger denominator)
        : this(numerator, denominator, false)
    { }

    [DebuggerStepThrough]
    private Rational(Rational numerator, Rational denominator)
        : this(numerator.numerator * denominator.Denominator, numerator.Denominator * denominator.numerator, false)
    { }

    private Rational(BigInteger numerator, BigInteger denominator, bool isIrreducible)
    {
        if (denominator < 0) //normalize to positive denominator
        {
            this.denominator = -denominator;
            this.numerator = -numerator;
        }
        else
        {
            this.numerator = numerator;
            this.denominator = denominator;
        }

        this.explicitConstructorCalled = true;
        this.isDefinitelyIrreducible = isIrreducible;
    }
    #endregion

    #region Instance properties
    public BigInteger Denominator { get { return explicitConstructorCalled ? denominator : 1; } } //We want default value to be zero, not NaN.

    public Rational FractionalPart
    {
        get
        {
            if (Denominator != 0)
            {
                if (IsProper(this))
                    return new Rational(numerator % Denominator, Denominator);

                return new Rational(BigInteger.Abs(numerator % Denominator), Denominator);
            }

            if (numerator == 0)
                return NaN;

            if (numerator > 0)
                return PositiveInfinity;

            return NegativeInfinity;
        }
    }

    public Rational IntegerPart
    {
        get
        {
            if (Denominator != 0)
                return (BigInteger)this;

            if (numerator == 0)
                return NaN;

            if (numerator > 0)
                return PositiveInfinity;

            return NegativeInfinity;
        }
    }

    public BigInteger Numerator { get { return numerator; } }

    public Rational Sign { get { return numerator.Sign; } }
    #endregion

    #region Instance methods
    public int CompareTo(Rational other)
    {
        //Even though neither infinities nor NaNs are equal to themselves, for 
        //comparison's sake it makes sense to return 0 when comparing PositiveInfinities
        //or NaNs, etc. The only other option would be to throw an exception...yuck.

        if (Rational.IsNaN(other))
            return Rational.IsNaN(this) ? 0 : 1;

        if (Rational.IsNaN(this))
            return Rational.IsNaN(other) ? 0 : -1;

        if (Rational.IsPositiveInfinity(this))
            return Rational.IsPositiveInfinity(other) ? 0 : 1;

        if (Rational.IsNegativeInfinity(this))
            return Rational.IsNegativeInfinity(other) ? 0 : -1;

        if (Rational.IsPositiveInfinity(other))
            return Rational.IsPositiveInfinity(this) ? 0 : -1;

        if (Rational.IsNegativeInfinity(other))
            return Rational.IsNegativeInfinity(this) ? 0 : 1;

        return (this.numerator * other.Denominator).CompareTo(this.Denominator * other.numerator);
    }

    public int CompareTo(object obj)
    {
        if (obj is Rational)
            return this.CompareTo((Rational)obj);

        if (obj == null)
            return 1;

        throw new ArgumentException("obj is not a RationalNumber.", "obj");
    }

    public bool Equals(Rational other)
    {
        if (this.Denominator == 0 || other.Denominator == 0) //By definition NaNs and infinities are not equal.
            return false;

        return this.numerator * other.Denominator == this.Denominator * other.numerator;
    }

    public override bool Equals(object obj)
    {
        if (obj is Rational)
            return this.Equals((Rational)obj);

        return false;
    }

    [DebuggerStepThrough]
    public override int GetHashCode()
    {
        if (isDefinitelyIrreducible)
            return this.numerator.GetHashCode() ^ this.Denominator.GetHashCode();

        return Rational.GetReducedForm(this).GetHashCode();
    }

    [DebuggerStepThrough]
    public override string ToString()
    {
        return ToString(null, null);
    }

    [DebuggerStepThrough]
    public string ToString(string format)
    {
        return ToString(format, null);
    }

    [DebuggerStepThrough]
    public string ToString(IFormatProvider formatProvider)
    {
        return ToString(null, formatProvider);
    }

    public string ToString(string format, IFormatProvider formatProvider)
    {
        try
        {
            if (formatProvider is RationalFormatProvider)
                return ((RationalFormatProvider)formatProvider).Format(format ?? "G", this, CultureInfo.CurrentCulture);

            var rationalFormatProvider = new RationalFormatProvider();
            return rationalFormatProvider.Format(format ?? "G", this, formatProvider ?? CultureInfo.CurrentCulture);
        }
        catch (FormatException e)
        {
            throw new FormatException(String.Format("The specified format string '{0}' is invalid.", format), e);
        }
    }
    #endregion

    #region Static properties
    public static bool IsInfinity(Rational rationalNumber)
    {
        return Rational.IsPositiveInfinity(rationalNumber) ||
                Rational.IsNegativeInfinity(rationalNumber);
    }

    public static bool IsIrreducible(Rational rationalNumber)
    {
        if (rationalNumber.isDefinitelyIrreducible)
            return true;

        if (rationalNumber.Denominator == 1 ||
            (rationalNumber.Denominator == 0 && (rationalNumber.numerator == 1 || rationalNumber.numerator == -1 || rationalNumber.numerator == 0)) ||
            rationalNumber.numerator.GreatestCommonDivisor(rationalNumber.Denominator) == 1)
            return true;

        return false;
    }

    public static bool IsPositiveInfinity(Rational rationalNumber)
    {
        return rationalNumber.Denominator == 0 && rationalNumber.numerator > 0; //Can not check using rationalNumber == positiveInfinity because by definition
                                                                                //infinities are not equal.
    }

    public static bool IsProper(Rational rationalNumber)
    {
        return BigInteger.Abs(rationalNumber.IntegerPart.numerator) < 1;
    }

    public static bool IsNaN(Rational rationalNumber)
    {
        return rationalNumber.Denominator == 0 && rationalNumber.numerator == 0; //Can not check using rationalNumber == naN because by definition NaN are not equal.
    }

    public static bool IsNegativeInfinity(Rational rationalNumber)
    {
        return rationalNumber.Denominator == 0 && rationalNumber.numerator < 0; //Can not check using rationalNumber == negativeInfinity because by definition
                                                                                //infinities are not equal.
    }
    #endregion

    #region Static methods
    public static Rational Abs(Rational number)
    {
        return new Rational(BigInteger.Abs(number.numerator), number.Denominator);
    }

    public static Rational Add(Rational left, Rational right, bool reduceOutput = false)
    {
        return reduceOutput ? Rational.GetReducedForm(left + right) : left + right;
    }

    public static Rational Ceiling(Rational number)
    {
        if (number.FractionalPart == Zero)
            return number.IntegerPart;

        if (number < Zero)
            return number.IntegerPart;

        return number.IntegerPart + 1;
    }

    public static Rational Divide(Rational left, Rational right, bool reduceOutput = false)
    {
        return reduceOutput ? Rational.GetReducedForm(left / right) : left / right;
    }

    public static Rational Floor(Rational number)
    {
        if (number.FractionalPart == Zero)
            return number.IntegerPart;

        if (number < Zero)
            return number.IntegerPart - 1;

        return number.IntegerPart;
    }

    public static Rational FromDouble(double target, double precision)
    {
        Rational result;

        if (!TryFromDouble(target, precision, out result))
            throw new ArgumentException("Can not find a rational aproximation with the specified precision.", "precision");

        return result;
    }

    public static Rational GetReciprocal(Rational rationalNumber)
    {
        return new Rational(rationalNumber.Denominator, rationalNumber.numerator, rationalNumber.isDefinitelyIrreducible);
    }

    public static Rational GetReducedForm(Rational rationalNumber)
    {
        if (rationalNumber.isDefinitelyIrreducible)
            return rationalNumber;

        var greatesCommonDivisor = rationalNumber.numerator.GreatestCommonDivisor(rationalNumber.Denominator);
        return new Rational(rationalNumber.numerator / greatesCommonDivisor, rationalNumber.Denominator / greatesCommonDivisor, true);
    }

    public static Rational Max(Rational first, Rational second)
    {
        if (first >= second)
            return first;

        return second;
    }

    public static Rational Min(Rational first, Rational second)
    {
        if (first <= second)
            return first;

        return second;
    }

    public static Rational Multiply(Rational left, Rational right, bool reduceOutput = false)
    {
        return reduceOutput ? Rational.GetReducedForm(left * right) : left * right;
    }

    public static Rational Negate(Rational right, bool reduceOutput = false)
    {
        return reduceOutput ? Rational.GetReducedForm(-right) : -right;
    }

    public static Rational Pow(Rational r, int n, bool reduceOutput = false)
    {
        if (Rational.IsNaN(r))
            return NaN;

        if (n > 0)
        {
            var result = new Rational(BigInteger.Pow(r.numerator, n), BigInteger.Pow(r.Denominator, n), false);
            return reduceOutput ? Rational.GetReducedForm(result) : result;
        }

        if (n < 0)
            return Pow(GetReciprocal(r), -n, reduceOutput);

        if (r == Zero || Rational.IsInfinity(r))
            return NaN;

        return One;
    }

    public static Rational Subtract(Rational left, Rational right, bool reduceOutput = false)
    {
        return reduceOutput ? Rational.GetReducedForm(left - right) : left - right;
    }

    public static double ToDouble(Rational rationalNumber)
    {
        return ((double)rationalNumber.numerator) / (double)rationalNumber.Denominator;
    }

    public static Rational Truncate(Rational number)
    {
        return number.IntegerPart;
    }

    public static bool TryFromDouble(double target, double precision, out Rational result)
    {
        //Continued fraction algorithm: http://en.wikipedia.org/wiki/Continued_fraction
        //Implemented recursively. Problem is figuring out when precision is met without unwinding each solution. Haven't figured out how to do that.
        //Current implementation computes rational number approximations for increasing algorithm depths until precision criteria is met, maximum depth is reached (fromDoubleMaxIterations)
        //or an OverflowException is thrown. Efficiency is probably improvable but this method will not be used in any performance critical code. No use in optimizing it unless there is
        //a good reason. Current implementation works reasonably well.

        result = Zero;
        int steps = 0;

        while (Math.Abs(target - Rational.ToDouble(result)) > precision)
        {
            if (steps > FROM_DOUBLE_MAX_ITERATIONS)
            {
                result = Zero;
                return false;
            }

            result = getNearestRationalNumber(target, 0, steps++);
        }

        return true;
    }

    private static Rational getNearestRationalNumber(double number, int currentStep, int maximumSteps)
    {
        var integerPart = (BigInteger)number;
        double fractionalPart = number - Math.Truncate(number);

        if (currentStep < maximumSteps && fractionalPart != 0)
            return integerPart + new Rational(1, getNearestRationalNumber(1 / fractionalPart, ++currentStep, maximumSteps));

        return new Rational(integerPart);
    }
    #endregion

    #region Operators
    public static explicit operator double (Rational rationalNumber) { return Rational.ToDouble(rationalNumber); }

    public static implicit operator Rational(BigInteger number) { return new Rational(number); }

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

    public static explicit operator BigInteger(Rational rationalNumber) { return rationalNumber.numerator / rationalNumber.Denominator; }

    public static bool operator ==(Rational left, Rational right) { return left.Equals(right); }

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

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

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

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

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

    public static Rational operator +(Rational right)
    {
        return right;
    }

    public static Rational operator -(Rational right)
    {
        return new Rational(-right.numerator, right.Denominator, right.isDefinitelyIrreducible);
    }

    public static Rational operator +(Rational left, Rational right)
    {
        if ((IsPositiveInfinity(left) && IsPositiveInfinity(right)) || //Otherwise the sum of two equally signed infinities would return NaN which is not correct.
            (IsNegativeInfinity(left) && IsNegativeInfinity(right)))
            return left;

        return new Rational(left.Numerator * right.Denominator + right.numerator * left.Denominator, left.Denominator * right.Denominator, false);
    }

    public static Rational operator -(Rational left, Rational right)
    {
        return left + (-right);
    }

    public static Rational operator *(Rational left, Rational right)
    {
        return new Rational(left.numerator * right.numerator, left.Denominator * right.Denominator, false);
    }

    public static Rational operator /(Rational left, Rational right)
    {
        if ((IsInfinity(left) && IsInfinity(right)) ||
            (left == Zero && right == 0))
            return NaN;

        return new Rational(left.numerator * right.Denominator, left.Denominator * right.numerator, false);
    }
    #endregion

   [DebuggerStepThrough]
    private class RationalFormatProvider : IFormatProvider, ICustomFormatter
    {
        public object GetFormat(Type formatType)
        {
            if (formatType == typeof(ICustomFormatter))
                return this;

            return null;
        }

        public string Format(string format, object arg, IFormatProvider formatProvider)
        {
            var upperFormat = format != null ? format.ToUpperInvariant().TrimStart() : "G";

            if (!(arg is Rational))
                return handleOtherFormats(format, arg, formatProvider);

            var rational = (Rational)arg;

            if (rational.Denominator == 0)
            {
                if (rational.numerator == 0)
                    return NAN_LITERAL;

                if (rational.numerator > 0)
                    return POSITIVE_INFINITY_LITERAL;

                return NEGATIVE_INFINITY_LITERAL;
            }

            string innerFormat = format;

            if (upperFormat[0] == 'M')
            {
                innerFormat = format.Replace('M', 'G');
                var integerPart = rational.IntegerPart.Numerator;

                if (integerPart != 0)
                {
                    var fractionalPart = rational.FractionalPart;
                    return string.Format("{0} [{1}/{2}]", integerPart.ToString(innerFormat, formatProvider),
                        BigInteger.Abs(fractionalPart.numerator).ToString(innerFormat, formatProvider), fractionalPart.Denominator.ToString(innerFormat, formatProvider));
                }
            }

            return string.Format("{0}/{1}", rational.numerator.ToString(innerFormat, formatProvider), rational.Denominator.ToString(innerFormat, formatProvider));
        }

        private string handleOtherFormats(string format, object arg, IFormatProvider formatProvider)
        {
            if (arg is IFormattable)
                return ((IFormattable)arg).ToString(format, formatProvider);

            if (arg != null)
                return arg.ToString();

            return String.Empty;
        }
    }
}

Tools class:

public static class Tools
{
    public static BigInteger LeastCommonMultiple(this BigInteger number1, BigInteger number2)
    {
        if (number1 == 0) return number2;
        if (number2 == 0) return number1;

        var positiveNumber2 = number2 < 0 ? BigInteger.Abs(number2) : number2;
        var positiveNumber1 = number1 < 0 ? BigInteger.Abs(number1) : number1;

        return positiveNumber1 / GreatestCommonDivisor(positiveNumber1, positiveNumber2) * positiveNumber2;
    }

    public static BigInteger GreatestCommonDivisor(this BigInteger number1, BigInteger number2)
    {
        var positiveNumber2 = number2 < 0 ? BigInteger.Abs(number2) : number2;
        var positiveNumber1 = number1 < 0 ? BigInteger.Abs(number1) : number1;

        if (positiveNumber1 == positiveNumber2)
            return positiveNumber1;

        if (positiveNumber1 == 0)
            return positiveNumber2;

        if (positiveNumber2 == 0)
            return positiveNumber1;

        if ((~positiveNumber1 & 1) != 0)
            if ((positiveNumber2 & 1) != 0)
                return GreatestCommonDivisor(positiveNumber1 >> 1, positiveNumber2);
            else
                return GreatestCommonDivisor(positiveNumber1 >> 1, positiveNumber2 >> 1) << 1;

        if ((~positiveNumber2 & 1) != 0)
            return GreatestCommonDivisor(positiveNumber1, positiveNumber2 >> 1);

        if (positiveNumber1 > positiveNumber2)
            return GreatestCommonDivisor((positiveNumber1 - positiveNumber2) >> 1, positiveNumber2);

        return GreatestCommonDivisor((positiveNumber2 - positiveNumber1) >> 1, positiveNumber1);
    }
}

Lastly, I'm not saying you have to use any of these. This is Code Review, not Code Use Only This Technique Ever.

\$\endgroup\$
  • 1
    \$\begingroup\$ "Constants (const) are typically all uppercase with words separated by underscores." Ten years ago, but in recent years these rules apply: "DO NOT use underscores, hyphens, or any other nonalphanumeric characters." and "Do use Pascal casing for all public member, type, and namespace names consisting of multiple words.". \$\endgroup\$ – BCdotWEB Jul 7 '15 at 14:34
  • 1
    \$\begingroup\$ @BCdotWEB That may be true, but personally, to me the upper-case const fields tell me immediately that they are const fields. It also helps me find them with intellisense quicker. I'm not saying it's the only way to do it by any means, but in my opinion it's the most effective. If the OP likes using PascalCase for const fields, that is his decision. I will add this information to the answer, however. \$\endgroup\$ – Der Kommissar Jul 7 '15 at 14:38
  • 1
    \$\begingroup\$ Thanks a lot for the in depth review. I really appreciate the time and effort. Completely agree with every single one of your suggestions. Normally I uppercase const fields but I decided to follow MS's guidelines this time. \$\endgroup\$ – InBetween Jul 7 '15 at 22:04
  • \$\begingroup\$ @InBetween I can respect that, as I said, these are all merely my personal recommendations. (I come from a heavy C/C++ background, constants were always completely uppercase.) Glad you found all of this information helpful. :) \$\endgroup\$ – Der Kommissar Jul 7 '15 at 22:05
5
\$\begingroup\$

I noticed this because naN looked really weird to my eyes. It's almost always seen as NaN. So I looked around a bit and found this.

   static readonly Rational one = new Rational(1);
   static readonly Rational zero = new Rational(0);
   static readonly Rational naN = new Rational(0, 0, true);
   static readonly Rational positiveInfinity = new Rational(1, 0, true);
   static readonly Rational negativeInfinity = new Rational(-1, 0, true);

These are all implicitly private, which explains the camelCasing, but should they be? These are the kinds of static members that usually get exposed to the outside world, particularly when creating structs. Client code is going to need these.

Never mind. After much digging through the code, I see that you are exposing them to the outside world through getters...

   public static Rational PositiveInfinity { get { return positiveInfinity; } }

   public static Rational NaN { get { return naN; } }

   public static Rational NegativeInfinity { get { return negativeInfinity; } }

   public static Rational Zero { get { return zero; } }

This is overkill in my opinion. The likelihood of ever needing to change the implementation is next to nil so having properties for these doesn't make much sense. It just clutters and confuses the code. Minimally, the public getters need to be declared much much closer to the private fields.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the input. Sadly in C# I can not declare Rational typed fields as const (compiler error CS0283). That is why I need to use static readonly. You can get more information on the subject here \$\endgroup\$ – InBetween Jul 3 '15 at 12:28
  • \$\begingroup\$ I fail to see what that has to do with anything here. Of course they can't be constant; they're not. That doesn't mean you can't directly expose these. Yes, I know that's "bad practice", but best practice isn't always best practice. If you really want to stick with the Getters, maybe upgrade to C# 6 where you could use a read only auto-property and initializer. \$\endgroup\$ – RubberDuck Jul 3 '15 at 12:32
  • \$\begingroup\$ Ok, I misunderstood what you were trying to say. Yes, directly exposing the readonly fields seems much more reasonable and as a matter of fact, its a widespread practice throughout the Framework; string.Empty. I will change the code accordingly. Thank you. \$\endgroup\$ – InBetween Jul 3 '15 at 12:37

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.