source: branches/HeuristicLab.Analysis.AlgorithmBehavior/liblrs/Testliblrs/FractionClass.cs @ 10198

  /*
  * Author: Syed Mehroz Alam
  * Email: smehrozalam@yahoo.com
  * URL: Programming Home "http://www.geocities.com/smehrozalam/" 
  *
  */

  using System;
  using System.Runtime.InteropServices;
  using System.Globalization;

  namespace Mehroz
  {
    /// <summary>
    /// Classes Contained:
    ///     Fraction
    ///     FractionException
    /// </summary>
      
    /// Class name: Fraction
    /// Developed by: Syed Mehroz Alam
    /// Email: mailto:smehrozalam@yahoo.com
    /// URL: http://www.geocities.com/smehrozalam/
    /// Changes: Marc C. Brooks  mailto:IDisposable@gmail.com
    ///          Jeffery Sax    http://www.extremeoptimization.com
    /// Version: 2.2
    /// 
    /// What's new in version 2.0:
    ///     *   Changed Numerator and Denominator from Int32(integer) to Int64(long) for increased range
    ///     *   renamed ConvertToString() to (overloaded) ToString()
    ///     *   added the capability of detecting/raising overflow exceptions
    ///     *   Fixed the bug that very small numbers e.g. 0.00000001 could not be converted to fraction
    ///     *   Other minor bugs fixed
    /// 
    /// What's new in version 2.1
    ///     *   overloaded user-defined conversions to/from Fractions
    ///
    /// What's new in version 2.2 - Marc C. Brooks   mailto:IDisposable@gmail.com
    ///     *   less overflows by finding the GCD for Add [Jeffery Sax] and Multiply [Marc C. Brooks]
    ///     *   understands and handles NaN, PositiveInfinity, NegativeInfinity just like double [Marc C. Brooks]
    ///     *   fixed several uses of int where long was correct [Marc C. Brooks]
    ///     *   made value-type (struct) [Jeffery Sax]
    ///     *   added ToInt32(), ToInt64() which throw for invalid (NaN, PositiveInfinity, NegativeInfinity) [Marc C. Brooks]
    ///     *   removed redundant Value property [Jeffery Sax]
    ///     *   added explicit conversion to Int32 and Int64 [Marc C. Brooks]
    ///     *   better handling of exceptions [Marc C. Brooks]
    ///     *   reorganize code, add XML doc and regions [Marc C. Brooks]
    ///     *   proper implementations of Equals [Marc C. Brooks, Jeffery Sax]
    ///     *   uses Math.Log(xx,2) and Math.Pow(xx,2) to get the best accuracy possible when converting doubles [Marc C. Brooks, Jeffery Sax]
    ///
    /// What's new in version 2.3 - Marc C. Brooks   mailto:IDisposable@gmail.com   01/10/2005
    ///     *   fixed double-to-fraction logic to use continued fraction rules to get best possible precistion [bug fix for Syed Mehroz Alam, idea from  Jeffery Sax]
    ///     * added static readonly values for NaN, PositiveInfinity, NegativeInfinity [idea from Jeffery Sax]
    ///     * moved comparisons into an implementation of IComparer [idea from Jeffery Sax]
    ///     * no longer throws for NaN(s) involved in Add, Subtract, Multiply, Divide operations [idea from Jeffery Sax]
    ///     *   added static readonly values for Zero, MinValue, MaxValue, Epsilon to better mirror double
    ///     *   added IsInfinity to better mirror double.
    ///     *   added Modulus and % operators
    ///
    /// Properties:
    ///     Numerator: Set/Get value for Numerator
    ///     Denominator:  Set/Get value for Numerator
    ///     [Note: If you Set either Property, the Fraction should be passed to ReduceFraction at some point.]
    /// 
    /// Constructors:
    ///     no arguments:   initializes fraction as 0/0 = NaN, so don't do that!
    ///     (Numerator, Denominator): initializes fraction with the given numerator and denominator 
    ///                               values and reduces
    ///     (long): initializes fraction with the given long value
    ///     (double):   initializes fraction with the given double value
    ///     (string):   initializes fraction with the given string value
    ///                 the string can be an in the form of and integer, double or fraction.
    ///                 e.g it can be like "123" or "123.321" or "123/456"
    /// 
    /// Public Methods (Description is given with respective methods' definitions)
    ///     Fraction ToFraction(long)
    ///     Fraction ToFraction(double)
    ///     Fraction ToFraction(string)
    ///     Int32 ToInt32()
    ///     Int64 ToInt64()
    ///     double ToDouble()
    ///     (override) string ToString()
    ///     Fraction Inverse()
    ///     Fraction Inverted(long)
    ///     Fraction Inverted(double)
    ///     ReduceFraction(ref Fraction)
    ///     CrossReducePair(ref Fraction, ref Fraction)
    ///     (override) Equals(object)
    ///     (override) GetHashCode()
    /// 
    /// Overloaded Operators (overloaded for Fractions, long and double)
    ///     Unary: -
    ///     Binary: +,-,*,/
    ///     Relational and Logical Operators: ==,!=,<,>,<=,>= (only == and != for long and doubles)
    /// 
    /// Overloaded user-defined conversions
    ///     Implicit:   From long/double/string to Fraction
    ///     Explicit:   From Fraction to long/double/string
    /// </summary>
    [Serializable, StructLayout(LayoutKind.Sequential)]
    public struct Fraction : IComparable, IFormattable
    {
      #region Constructors
      /// <summary>
      /// Construct a Fraction from an integral value
      /// </summary>
      /// <param name="wholeNumber">The value (eventual numerator)</param>
      /// <remarks>The denominator will be 1</remarks>
      public Fraction(long wholeNumber)
      {
        if (wholeNumber == long.MinValue)
          wholeNumber++;  // prevent serious issues later..

        m_Numerator = wholeNumber;
        m_Denominator = 1;
        // no reducing required, we're a whole number
      }
      
      /// <summary>
      /// Construct a Fraction from a floating-point value
      /// </summary>
      /// <param name="floatingPointNumber">The value</param>
      public Fraction(double floatingPointNumber)
      {
        this = ToFraction(floatingPointNumber);
      }
          
      /// <summary>
      /// Construct a Fraction from a string in any legal format
      /// </summary>
      /// <param name="inValue">A string with a legal fraction input format</param>
      /// <remarks>Will reduce the fraction to smallest possible denominator</remarks>
      /// <see>ToFraction(string strValue)</see>
      public Fraction(string inValue)
      {
        this = ToFraction(inValue);
      }
          
      /// <summary>
      /// Construct a Fraction from a numerator, denominator pair
      /// </summary>
      /// <param name="numerator">The numerator (top number)</param>
      /// <param name="denominator">The denominator (bottom number)</param>
      /// <remarks>Will reduce the fraction to smallest possible denominator</remarks>
      public Fraction(long numerator, long denominator)
      {
        if (numerator == long.MinValue)
          numerator++;  // prevent serious issues later..

        if (denominator == long.MinValue)
          denominator++;  // prevent serious issues later..

        m_Numerator = numerator;
        m_Denominator = denominator;
        ReduceFraction(ref this);
      }

      /// <summary>
      /// Private constructor to synthesize a Fraction for indeterminates (NaN and infinites)
      /// </summary>
      /// <param name="type">Kind of inderterminate</param>
      private Fraction(Indeterminates type)
      {
        m_Numerator = (long)type;
        m_Denominator = 0;
        // do NOT reduce, we're clean as can be!
      }
      #endregion

      #region Properties
      /// <summary>
      /// The 'top' part of the fraction
      /// </summary>
      /// <example>For 3/4ths, this is the 3</example>
      public long Numerator
      {
        get 
        {
          return m_Numerator;
        }
        set
        {
          m_Numerator = value;
        }
      }

      /// <summary>
      /// The 'bottom' part of the fraction
      /// </summary>
      /// <example>For 3/4ths, this is the 4</example>
      public long Denominator
      {
        get
        {
          return m_Denominator;
        }
        set
        {
          m_Denominator = value;
        }
      }
      #endregion

      #region Expose constants
      public static readonly Fraction NaN = new Fraction(Indeterminates.NaN);
      public static readonly Fraction PositiveInfinity = new Fraction(Indeterminates.PositiveInfinity);
      public static readonly Fraction NegativeInfinity = new Fraction(Indeterminates.NegativeInfinity);
      public static readonly Fraction Zero = new Fraction(0,1);
      public static readonly Fraction Epsilon = new Fraction(1, Int64.MaxValue);
      private static readonly double EpsilonDouble = 1.0 / Int64.MaxValue;
      public static readonly Fraction MaxValue = new Fraction(Int64.MaxValue, 1);
      public static readonly Fraction MinValue = new Fraction(Int64.MinValue, 1);
      #endregion

      #region Explicit conversions
      #region To primitives
      /// <summary>
      /// Get the integral value of the Fraction object as int/Int32
      /// </summary>
      /// <returns>The (approximate) integer value</returns>
      /// <remarks>If the value is not a true integer, the fractional part is discarded
      /// (truncated toward zero). If the valid exceeds the range of an Int32 and exception is thrown.</remarks>
      /// <exception cref="FractionException">Will throw a FractionException for NaN, PositiveInfinity
      /// or NegativeInfinity with the InnerException set to a System.NotFiniteNumberException.</exception>
      /// <exception cref="OverflowException" Will throw a System.OverflowException if the value is too
      /// large or small to be represented as an Int32.</exception>
      public Int32 ToInt32()
      {
        if (this.m_Denominator == 0)
        {
          throw new FractionException(string.Format("Cannot convert {0} to Int32", IndeterminateTypeName(this.m_Numerator)), new System.NotFiniteNumberException());
        }

        long bestGuess = this.m_Numerator / this.m_Denominator;

        if (bestGuess > Int32.MaxValue || bestGuess < Int32.MinValue)
        {
          throw new FractionException("Cannot convert to Int32", new System.OverflowException());
        }

        return (Int32)bestGuess;
      }

      /// <summary>
      /// Get the integral value of the Fraction object as long/Int64
      /// </summary>
      /// <returns>The (approximate) integer value</returns>
      /// <remarks>If the value is not a true integer, the fractional part is discarded
      /// (truncated toward zero). If the valid exceeds the range of an Int32, no special
      /// handling is guaranteed.</remarks>
      /// <exception cref="FractionException">Will throw a FractionException for NaN, PositiveInfinity
      /// or NegativeInfinity with the InnerException set to a System.NotFiniteNumberException.</exception>
      public Int64 ToInt64()
      {
        if (this.m_Denominator == 0)
        {
          throw new FractionException(string.Format("Cannot convert {0} to Int64", IndeterminateTypeName(this.m_Numerator)), new System.NotFiniteNumberException());
        }

        return this.m_Numerator / this.m_Denominator;
      }

      /// <summary>
      /// Get the value of the Fraction object as double with full support for NaNs and infinities
      /// </summary>
      /// <returns>The decimal representation of the Fraction, or double.NaN, double.NegativeInfinity
      /// or double.PositiveInfinity</returns>
      public double ToDouble()
      {
        if (this.m_Denominator == 1)
          return this.m_Numerator;
        else if (this.m_Denominator == 0)
        {
          switch (NormalizeIndeterminate(this.m_Numerator))
          {
            case Indeterminates.NegativeInfinity:
              return double.NegativeInfinity;

            case Indeterminates.PositiveInfinity:
              return double.PositiveInfinity;

            case Indeterminates.NaN:
            default:    // this can't happen
              return double.NaN;
          }
        }
        else
        {
          return (double)this.m_Numerator / (double)this.m_Denominator;
        }
      }

      /// <summary>
      /// Get the value of the Fraction as a string, with proper representation for NaNs and infinites
      /// </summary>
      /// <returns>The string representation of the Fraction, or the culture-specific representations of
      /// NaN, PositiveInfinity or NegativeInfinity.</returns>
      /// <remarks>The current culture determines the textual representation the Indeterminates</remarks>
      public override string ToString()
      {
        if (this.m_Denominator == 1)
        {
          return this.m_Numerator.ToString();
        }
        else if (this.m_Denominator == 0)
        {
          return IndeterminateTypeName(this.m_Numerator);
        }
        else
        {
          return this.m_Numerator.ToString() + "/" + this.m_Denominator.ToString();
        }
      }
      #endregion

      #region From primitives
      /// <summary>
      /// Converts a long value to the exact Fraction
      /// </summary>
      /// <param name="inValue">The long to convert</param>
      /// <returns>An exact representation of the value</returns>
      public static Fraction ToFraction(long inValue)
      {
        return new Fraction(inValue);
      }

      /// <summary>
      /// Converts a double value to the approximate Fraction
      /// </summary>
      /// <param name="inValue">The double to convert</param>
      /// <returns>A best-fit representation of the value</returns>
      /// <remarks>Supports double.NaN, double.PositiveInfinity and double.NegativeInfinity</remarks>
      public static Fraction ToFraction(double inValue)
      {
        // it's one of the indeterminates... which?
        if (double.IsNaN(inValue))
          return NaN;
        else if (double.IsNegativeInfinity(inValue))
          return NegativeInfinity;
        else if (double.IsPositiveInfinity(inValue))
          return PositiveInfinity;
        else if (inValue == 0.0d)
          return Zero;

        if (inValue > Int64.MaxValue)
          throw new OverflowException(string.Format("Double {0} too large", inValue));

        if (inValue < -Int64.MaxValue)
          throw new OverflowException(string.Format("Double {0} too small", inValue));

        if (-EpsilonDouble < inValue && inValue < EpsilonDouble)
          throw new ArithmeticException(string.Format("Double {0} cannot be represented", inValue));

        int sign = Math.Sign(inValue);
        inValue = Math.Abs(inValue);

        return ConvertPositiveDouble(sign, inValue);
      }

      /// <summary>
      /// Converts a string to the corresponding reduced fraction
      /// </summary>
      /// <param name="inValue">The string representation of a fractional value</param>
      /// <returns>The Fraction that represents the string</returns>
      /// <remarks>Four forms are supported, as a plain integer, as a double, or as Numerator/Denominator
      /// and the representations for NaN and the infinites</remarks>
      /// <example>"123" = 123/1 and "1.25" = 5/4 and "10/36" = 5/13 and NaN = 0/0 and
      /// PositiveInfinity = 1/0 and NegativeInfinity = -1/0</example>
      public static Fraction ToFraction(string inValue)
      {
        if (inValue == null || inValue == string.Empty)
          throw new ArgumentNullException("inValue");

        // could also be NumberFormatInfo.InvariantInfo
        NumberFormatInfo info = NumberFormatInfo.CurrentInfo;

        // Is it one of the special symbols for NaN and such...
        string trimmedValue = inValue.Trim();

        if (trimmedValue == info.NaNSymbol)
          return NaN;
        else if (trimmedValue == info.PositiveInfinitySymbol)
          return PositiveInfinity;
        else if (trimmedValue == info.NegativeInfinitySymbol)
          return NegativeInfinity;
        else
        {
          // Not special, is it a Fraction?
          int slashPos = inValue.IndexOf('/');

          if (slashPos > -1)
          {
            // string is in the form of Numerator/Denominator
            long numerator = Convert.ToInt64(inValue.Substring(0, slashPos));
            long denominator = Convert.ToInt64(inValue.Substring(slashPos + 1));

            return new Fraction(numerator, denominator);
          }
          else
          {
            // the string is not in the form of a fraction
            // hopefully it is double or integer, do we see a decimal point?
            int decimalPos = inValue.IndexOf(info.CurrencyDecimalSeparator);

            if (decimalPos > -1)
              return new Fraction(Convert.ToDouble(inValue));
            else
              return new Fraction(Convert.ToInt64(inValue));
          }
        }
      }
      #endregion
      #endregion

      #region Indeterminate classifications
      /// <summary>
      /// Determines if a Fraction represents a Not-a-Number
      /// </summary>
      /// <returns>True if the Fraction is a NaN</returns>
      public bool IsNaN()
      {
        if (this.m_Denominator == 0 
          && NormalizeIndeterminate(this.m_Numerator) == Indeterminates.NaN)
          return true;
        else
          return false;
      }

      /// <summary>
      /// Determines if a Fraction represents Any Infinity
      /// </summary>
      /// <returns>True if the Fraction is Positive Infinity or Negative Infinity</returns>
      public bool IsInfinity()
      {
        if (this.m_Denominator == 0
          && NormalizeIndeterminate(this.m_Numerator) != Indeterminates.NaN)
          return true;
        else
          return false;
      }

      /// <summary>
      /// Determines if a Fraction represents Positive Infinity
      /// </summary>
      /// <returns>True if the Fraction is Positive Infinity</returns>
      public bool IsPositiveInfinity()
      {
        if (this.m_Denominator == 0
          && NormalizeIndeterminate(this.m_Numerator) == Indeterminates.PositiveInfinity)
          return true;
        else
          return false;
      }

      /// <summary>
      /// Determines if a Fraction represents Negative Infinity
      /// </summary>
      /// <returns>True if the Fraction is Negative Infinity</returns>
      public bool IsNegativeInfinity()
      {
        if (this.m_Denominator == 0
          && NormalizeIndeterminate(this.m_Numerator) == Indeterminates.NegativeInfinity)
          return true;
        else
          return false;
      }
      #endregion

      #region Inversion
      /// <summary>
      /// Inverts a Fraction
      /// </summary>
      /// <returns>The inverted Fraction (with Denominator over Numerator)</returns>
      /// <remarks>Does NOT throw for zero Numerators as later use of the fraction will catch the error.</remarks>
      public Fraction Inverse()
      {
        // don't use the obvious constructor because we do not want it normalized at this time
        Fraction frac = new Fraction();

        frac.m_Numerator = this.m_Denominator;
        frac.m_Denominator = this.m_Numerator;
        return frac;
      }

      /// <summary>
      /// Creates an inverted Fraction
      /// </summary>
      /// <returns>The inverted Fraction (with Denominator over Numerator)</returns>
      /// <remarks>Does NOT throw for zero Numerators as later use of the fraction will catch the error.</remarks>
      public static Fraction Inverted(long value)
      {
        Fraction frac = new Fraction(value);
        return frac.Inverse();
      }

      /// <summary>
      /// Creates an inverted Fraction
      /// </summary>
      /// <returns>The inverted Fraction (with Denominator over Numerator)</returns>
      /// <remarks>Does NOT throw for zero Numerators as later use of the fraction will catch the error.</remarks>
      public static Fraction Inverted(double value)
      {
        Fraction frac = new Fraction(value);
        return frac.Inverse();
      }
      #endregion

      #region Operators
      #region Unary Negation operator
      /// <summary>
      /// Negates the Fraction
      /// </summary>
      /// <param name="left">The Fraction to negate</param>
      /// <returns>The negative version of the Fraction</returns>
      public static Fraction operator -(Fraction left)
      {
        return Negate(left);
      }
      #endregion

      #region Addition operators
      public static Fraction operator +(Fraction left, Fraction right)
      {
        return Add(left, right);
      }
      
      public static Fraction operator +(long left, Fraction right)
      {
        return Add(new Fraction(left), right);
      }
      
      public static Fraction operator +(Fraction left, long right)
      {
        return Add(left, new Fraction(right));
      }

      public static Fraction operator +(double left, Fraction right)
      {
        return Add(ToFraction(left), right);
      }
      
      public static Fraction operator +(Fraction left, double right)
      {
        return Add(left, ToFraction(right));
      }
      #endregion

      #region Subtraction operators
      public static Fraction operator -(Fraction left, Fraction right)
      {
        return Add(left, - right);
      }
      
      public static Fraction operator -(long left, Fraction right)
      {
        return Add(new Fraction(left), - right);
      }
      
      public static Fraction operator -(Fraction left, long right)
      {
        return Add(left, new Fraction(- right));
      }

      public static Fraction operator -(double left, Fraction right)
      {
        return Add(ToFraction(left), - right);
      }
      
      public static Fraction operator -(Fraction left, double right)
      {
        return Add(left, ToFraction(- right));
      }
      #endregion

      #region Multiplication operators
      public static Fraction operator *(Fraction left, Fraction right)
      {
        return Multiply(left, right);
      }
      
      public static Fraction operator *(long left, Fraction right)
      {
        return Multiply(new Fraction(left), right);
      }
      
      public static Fraction operator *(Fraction left, long right)
      {
        return Multiply(left, new Fraction(right));
      }
      
      public static Fraction operator *(double left, Fraction right)
      {
        return Multiply(ToFraction(left), right);
      }
      
      public static Fraction operator *(Fraction left, double right)
      {
        return Multiply(left, ToFraction(right));
      }
      #endregion

      #region Division operators
      public static Fraction operator /(Fraction left, Fraction right)
      {
        return Multiply(left, right.Inverse());
      }
      
      public static Fraction operator /(long left, Fraction right)
      {
        return Multiply(new Fraction(left), right.Inverse());
      }
      
      public static Fraction operator /(Fraction left, long right)
      {
        return Multiply(left, Inverted(right));
      }
      
      public static Fraction operator /(double left, Fraction right)
      {
        return Multiply(ToFraction(left), right.Inverse());
      }
      
      public static Fraction operator /(Fraction left, double right)
      {
        return Multiply(left, Inverted(right));
      }
      #endregion

      #region Modulus operators
      public static Fraction operator %(Fraction left, Fraction right)
      {
        return Modulus(left, right);
      }
      
      public static Fraction operator %(long left, Fraction right)
      {
        return Modulus(new Fraction(left), right);
      }
      
      public static Fraction operator %(Fraction left, long right)
      {
        return Modulus(left, right);
      }
      
      public static Fraction operator %(double left, Fraction right)
      {
        return Modulus(ToFraction(left), right);
      }
      
      public static Fraction operator %(Fraction left, double right)
      {
        return Modulus(left, right);
      }
      #endregion

      #region Equal operators
      public static bool operator ==(Fraction left, Fraction right)
      {
        return left.CompareEquality(right, false);
      }

      public static bool operator ==(Fraction left, long right)
      {
        return left.CompareEquality(new Fraction(right), false);
      }

      public static bool operator ==(Fraction left, double right)
      {
        return left.CompareEquality(new Fraction(right), false);
      }
      #endregion

      #region Not-equal operators
      public static bool operator !=(Fraction left, Fraction right)
      {
        return left.CompareEquality(right, true);
      }

      public static bool operator !=(Fraction left, long right)
      {
        return left.CompareEquality(new Fraction(right), true);
      }
          
      public static bool operator !=(Fraction left, double right)
      {
        return left.CompareEquality(new Fraction(right), true);
      }
      #endregion

      #region Inequality operators
      /// <summary>
      /// Compares two Fractions to see if left is less than right
      /// </summary>
      /// <param name="left">The first Fraction</param>
      /// <param name="right">The second Fraction</param>
      /// <returns>True if <paramref name="left">left</paramref> is less
      /// than <paramref name="right">right</paramref></returns>
      /// <remarks>Special handling for indeterminates exists. <see>IndeterminateLess</see></remarks>
      /// <exception cref="FractionException">Throws an error if overflows occur while computing the 
      /// difference with an InnerException of OverflowException</exception>
      public static bool operator <(Fraction left, Fraction right)
      {
        return left.CompareTo(right) < 0;
      }

      /// <summary>
      /// Compares two Fractions to see if left is greater than right
      /// </summary>
      /// <param name="left">The first Fraction</param>
      /// <param name="right">The second Fraction</param>
      /// <returns>True if <paramref name="left">left</paramref> is greater
      /// than <paramref name="right">right</paramref></returns>
      /// <remarks>Special handling for indeterminates exists. <see>IndeterminateLess</see></remarks>
      /// <exception cref="FractionException">Throws an error if overflows occur while computing the 
      /// difference with an InnerException of OverflowException</exception>
      public static bool operator >(Fraction left, Fraction right)
      {
        return left.CompareTo(right) > 0;
      }

      /// <summary>
      /// Compares two Fractions to see if left is less than or equal to right
      /// </summary>
      /// <param name="left">The first Fraction</param>
      /// <param name="right">The second Fraction</param>
      /// <returns>True if <paramref name="left">left</paramref> is less than or 
      /// equal to <paramref name="right">right</paramref></returns>
      /// <remarks>Special handling for indeterminates exists. <see>IndeterminateLessEqual</see></remarks>
      /// <exception cref="FractionException">Throws an error if overflows occur while computing the 
      /// difference with an InnerException of OverflowException</exception>
      public static bool operator <=(Fraction left, Fraction right)
      {
        return left.CompareTo(right) <= 0;
      }
          
      /// <summary>
      /// Compares two Fractions to see if left is greater than or equal to right
      /// </summary>
      /// <param name="left">The first Fraction</param>
      /// <param name="right">The second Fraction</param>
      /// <returns>True if <paramref name="left">left</paramref> is greater than or 
      /// equal to <paramref name="right">right</paramref></returns>
      /// <remarks>Special handling for indeterminates exists. <see>IndeterminateLessEqual</see></remarks>
      /// <exception cref="FractionException">Throws an error if overflows occur while computing the 
      /// difference with an InnerException of OverflowException</exception>
      public static bool operator >=(Fraction left, Fraction right)
      {
        return left.CompareTo(right) >= 0;
      }
      #endregion

      #region Implict conversion from primitive operators
      /// <summary>
      /// Implicit conversion of a long integral value to a Fraction
      /// </summary>
      /// <param name="value">The long integral value to convert</param>
      /// <returns>A Fraction whose denominator is 1</returns>
      public static implicit operator Fraction(long value)
      {
        return new Fraction(value);
      }

      /// <summary>
      /// Implicit conversion of a double floating point value to a Fraction
      /// </summary>
      /// <param name="value">The double value to convert</param>
      /// <returns>A reduced Fraction</returns>
      public static implicit operator Fraction(double value)
      {
        return new Fraction(value);
      }

      /// <summary>
      /// Implicit conversion of a string to a Fraction
      /// </summary>
      /// <param name="value">The string to convert</param>
      /// <returns>A reduced Fraction</returns>
      public static implicit operator Fraction(string value)
      {
        return new Fraction(value);
      }
      #endregion

      #region Explicit converstion to primitive operators
      /// <summary>
      /// Explicit conversion from a Fraction to an integer
      /// </summary>
      /// <param name="frac">the Fraction to convert</param>
      /// <returns>The integral representation of the Fraction</returns>
      public static explicit operator int(Fraction frac)
      {
        return frac.ToInt32();
      }

      /// <summary>
      /// Explicit conversion from a Fraction to an integer
      /// </summary>
      /// <param name="frac">The Fraction to convert</param>
      /// <returns>The integral representation of the Fraction</returns>
      public static explicit operator long(Fraction frac)
      {
        return frac.ToInt64();
      }

      /// <summary>
      /// Explicit conversion from a Fraction to a double floating-point value
      /// </summary>
      /// <param name="frac">The Fraction to convert</param>
      /// <returns>The double representation of the Fraction</returns>
      public static explicit operator double(Fraction frac)
      {
        return frac.ToDouble();
      }

      /// <summary>
      /// Explicit conversion from a Fraction to a string
      /// </summary>
      /// <param name="frac">the Fraction to convert</param>
      /// <returns>The string representation of the Fraction</returns>
      public static implicit operator string(Fraction frac)
      {
        return frac.ToString();
      }
      #endregion
      #endregion

      #region Equals and GetHashCode overrides
      /// <summary>
      /// Compares for equality the current Fraction to the value passed.
      /// </summary>
      /// <param name="obj">A  Fraction,</param>
      /// <returns>True if the value equals the current fraction, false otherwise (including for
      /// non-Fraction types or null object.</returns>
      public override bool Equals(object obj)
      {
        if (obj == null || ! (obj is Fraction))
          return false;

        try 
        {
          Fraction right = (Fraction)obj;
          return this.CompareEquality(right, false);
        }
        catch
        {
          // can't throw in an Equals!
          return false;
        }
      }
          
      /// <summary>
      /// Returns a hash code generated from the current Fraction
      /// </summary>
      /// <returns>The hash code</returns>
      /// <remarks>Reduces (in-place) the Fraction first.</remarks>
      public override int GetHashCode()
      {
        // insure we're as close to normalized as possible first
        ReduceFraction(ref this);

        int numeratorHash = this.m_Numerator.GetHashCode();
        int denominatorHash = this.m_Denominator.GetHashCode();

        return (numeratorHash ^ denominatorHash);
      }
      #endregion

      #region IComparable member and type-specific version
      /// <summary>
      /// Compares an object to this Fraction
      /// </summary>
      /// <param name="obj">The object to compare against (null is less than everything)</param>
      /// <returns>-1 if this is less than <paramref name="obj"></paramref>,
      ///  0 if they are equal,
      ///  1 if this is greater than <paramref name="obj"></paramref></returns>
      /// <remarks>Will convert an object from longs, doubles, and strings as this is a value-type.</remarks>
      public int CompareTo(object obj)
      {
        if (obj == null)
          return 1; // null is less than anything

        Fraction right;

        if (obj is Fraction)
          right = (Fraction)obj;
        else if (obj is long)
          right = (long)obj;
        else if (obj is double)
          right = (double)obj;
        else if (obj is string)
          right = (string)obj;
        else
          throw new ArgumentException("Must be convertible to Fraction", "obj");

        return this.CompareTo(right);
      }

      /// <summary>
      /// Compares this Fraction to another Fraction
      /// </summary>
      /// <param name="right">The Fraction to compare against</param>
      /// <returns>-1 if this is less than <paramref name="right"></paramref>,
      ///  0 if they are equal,
      ///  1 if this is greater than <paramref name="right"></paramref></returns>
      public int CompareTo(Fraction right)
      {
        // if left is an indeterminate, punt to the helper...
        if (this.m_Denominator == 0)
        {
          return IndeterminantCompare(NormalizeIndeterminate(this.m_Numerator), right);
        }

        // if right is an indeterminate, punt to the helper...
        if (right.m_Denominator == 0)
        {
          // note sign-flip...
          return - IndeterminantCompare(NormalizeIndeterminate(right.m_Numerator), this);
        }

        // they're both normal Fractions
        CrossReducePair(ref this, ref right);

        try
        {
          checked
          {
            long leftScale = this.m_Numerator * right.m_Denominator;
            long rightScale = this.m_Denominator * right.m_Numerator;

            if (leftScale < rightScale)
              return -1;
            else if (leftScale > rightScale)
              return 1;
            else
              return 0;
          }
        }
        catch (Exception e)
        {
          throw new FractionException(string.Format("CompareTo({0}, {1}) error", this, right), e);
        }
      }
      #endregion

      #region IFormattable Members
      string System.IFormattable.ToString(string format, IFormatProvider formatProvider)
      {
        return this.m_Numerator.ToString(format, formatProvider) + "/" + this.m_Denominator.ToString(format, formatProvider);
      }
      #endregion

      #region Reduction
      /// <summary>
      /// Reduces (simplifies) a Fraction by dividing down to lowest possible denominator (via GCD)
      /// </summary>
      /// <param name="frac">The Fraction to be reduced [WILL BE MODIFIED IN PLACE]</param>
      /// <remarks>Modifies the input arguments in-place! Will normalize the NaN and infinites
      /// representation. Will set Denominator to 1 for any zero numerator. Moves sign to the
      /// Numerator.</remarks>
      /// <example>2/4 will be reduced to 1/2</example>
      public static void ReduceFraction(ref Fraction frac)
      {
        // clean up the NaNs and infinites
        if (frac.m_Denominator == 0)
        {
          frac.m_Numerator = (long)NormalizeIndeterminate(frac.m_Numerator);
          return;
        }

        // all forms of zero are alike.
        if (frac.m_Numerator == 0)
        {
          frac.m_Denominator = 1;
          return;
        }
              
        long iGCD = GCD(frac.m_Numerator, frac.m_Denominator);
        frac.m_Numerator /= iGCD;
        frac.m_Denominator /= iGCD;
          
        // if negative sign in denominator
        if ( frac.m_Denominator < 0 )
        {
          //move negative sign to numerator
          frac.m_Numerator = - frac.m_Numerator;
          frac.m_Denominator = - frac.m_Denominator;  
        }
      }

      /// <summary>
      /// Cross-reduces a pair of Fractions so that we have the best GCD-reduced values for multiplication
      /// </summary>
      /// <param name="frac1">The first Fraction [WILL BE MODIFIED IN PLACE]</param>
      /// <param name="frac2">The second Fraction [WILL BE MODIFIED IN PLACE]</param>
      /// <remarks>Modifies the input arguments in-place!</remarks>
      /// <example>(3/4, 5/9) = (1/4, 5/3)</example>
      public static void CrossReducePair(ref Fraction frac1, ref Fraction frac2)
      {
        // leave the indeterminates alone!
        if (frac1.m_Denominator == 0 || frac2.m_Denominator == 0)
          return;

        long gcdTop = GCD(frac1.m_Numerator, frac2.m_Denominator);
        frac1.m_Numerator = frac1.m_Numerator / gcdTop;
        frac2.m_Denominator = frac2.m_Denominator / gcdTop;

        long gcdBottom = GCD(frac1.m_Denominator, frac2.m_Numerator);
        frac2.m_Numerator = frac2.m_Numerator / gcdBottom;
        frac1.m_Denominator = frac1.m_Denominator / gcdBottom;
      }
      #endregion

      #region Implementation
      #region Convert a double to a fraction
      private static Fraction ConvertPositiveDouble(int sign, double inValue)
      {
        // Shamelessly stolen from http://homepage.smc.edu/kennedy_john/CONFRAC.PDF
        // with AccuracyFactor == double.Episilon
        long fractionNumerator = (long)inValue;
        double fractionDenominator = 1;
        double previousDenominator = 0;
        double remainingDigits = inValue;
        int maxIterations = 594;  // found at http://www.ozgrid.com/forum/archive/index.php/t-22530.html

        while (remainingDigits != Math.Floor(remainingDigits) 
          && Math.Abs(inValue - (fractionNumerator / fractionDenominator)) > double.Epsilon)
        {
          remainingDigits = 1.0 / (remainingDigits - Math.Floor(remainingDigits));

          double scratch = fractionDenominator;

          fractionDenominator =(Math.Floor(remainingDigits) * fractionDenominator) + previousDenominator;
          fractionNumerator = (long)(inValue * fractionDenominator + 0.5);

          previousDenominator = scratch;

          if (maxIterations-- < 0)
            break;
        }

        return new Fraction(fractionNumerator * sign, (long)fractionDenominator);
      }
      #endregion

      #region Equality helper
      /// <summary>
      /// Compares for equality the current Fraction to the value passed.
      /// </summary>
      /// <param name="right">A Fraction to compare against</param>
      /// <param name="notEqualCheck">If true, we're looking for not-equal</param>
      /// <returns>True if the <paramref name="right"></paramref> equals the current 
      /// fraction, false otherwise. If comparing two NaNs, they are always equal AND
      /// not-equal.</returns>
      private bool CompareEquality(Fraction right, bool notEqualCheck)
      {
        // insure we're normalized first
        ReduceFraction(ref this);

        // now normalize the comperand
        ReduceFraction(ref right);

        if (this.m_Numerator == right.m_Numerator && this.m_Denominator == right.m_Denominator)
        {
          // special-case rule, two NaNs are always both equal
          if (notEqualCheck && this.IsNaN())
            return true;
          else
            return ! notEqualCheck;
        }
        else
        {
          return notEqualCheck;
        }
      }
      #endregion

      #region Comparison helper
      /// <summary>
      /// Determines how this Fraction, of an indeterminate type, compares to another Fraction
      /// </summary>
      /// <param name="leftType">What kind of indeterminate</param>
      /// <param name="right">The other Fraction to compare against</param>
      /// <returns>-1 if this is less than <paramref name="right"></paramref>,
      ///  0 if they are equal,
      ///  1 if this is greater than <paramref name="right"></paramref></returns>
      /// <remarks>NaN is less than anything except NaN and Negative Infinity. Negative Infinity is less
      /// than anything except Negative Infinity. Positive Infinity is greater than anything except
      /// Positive Infinity.</remarks>
      private static int IndeterminantCompare(Indeterminates leftType, Fraction right)
      {
        switch (leftType)
        {
          case Indeterminates.NaN:
            // A NaN is...
            if (right.IsNaN())
              return 0; // equal to a NaN
            else if (right.IsNegativeInfinity())
              return 1; // great than Negative Infinity
            else
              return -1;  // less than anything else

          case Indeterminates.NegativeInfinity:
            // Negative Infinity is...
            if (right.IsNegativeInfinity())
              return 0; // equal to Negative Infinity
            else
              return -1;  // less than anything else

          case Indeterminates.PositiveInfinity:
            if (right.IsPositiveInfinity())
              return 0; // equal to Positive Infinity
            else
              return 1; // greater than anything else

          default:
            // this CAN'T happen, something VERY wrong is going on...
            return 0;
        }
      }
      #endregion

      #region Math helpers
      /// <summary>
      /// Negates the Fraction
      /// </summary>
      /// <param name="frac">Value to negate</param>
      /// <returns>A new Fraction that is sign-flipped from the input</returns>
      private static Fraction Negate(Fraction frac)
      {
        // for a NaN, it's still a NaN
        return new Fraction( - frac.m_Numerator, frac.m_Denominator);
      }

      /// <summary>
      /// Adds two Fractions
      /// </summary>
      /// <param name="left">A Fraction</param>
      /// <param name="right">Another Fraction</param>
      /// <returns>Sum of the Fractions. Returns NaN if either Fraction is a NaN.</returns>
      /// <exception cref="FractionException">Will throw if an overflow occurs when computing the
      /// GCD-normalized values.</exception>
      private static Fraction Add(Fraction left, Fraction right)
      {
        if (left.IsNaN() || right.IsNaN())
          return NaN;

        long gcd = GCD(left.m_Denominator, right.m_Denominator); // cannot return less than 1
        long leftDenominator = left.m_Denominator / gcd;
        long rightDenominator = right.m_Denominator / gcd;

        try
        {
          checked
          {
            long numerator = left.m_Numerator * rightDenominator + right.m_Numerator * leftDenominator;
            long denominator = leftDenominator * rightDenominator * gcd;

            return new Fraction(numerator, denominator);
          }
        }
        catch (Exception e)
        {
          throw new FractionException("Add error", e);
        }
      }
      
      /// <summary>
      /// Multiplies two Fractions
      /// </summary>
      /// <param name="left">A Fraction</param>
      /// <param name="right">Another Fraction</param>
      /// <returns>Product of the Fractions. Returns NaN if either Fraction is a NaN.</returns>
      /// <exception cref="FractionException">Will throw if an overflow occurs. Does a cross-reduce to 
      /// insure only the unavoidable overflows occur.</exception>
      private static Fraction Multiply(Fraction left, Fraction right)
      {
        if (left.IsNaN() || right.IsNaN())
          return NaN;

        // this would be unsafe if we were not a ValueType, because we would be changing the
        // caller's values.  If we change back to a class, must use temporaries
        CrossReducePair(ref left, ref right);

        try
        {
          checked
          {
            long numerator = left.m_Numerator * right.m_Numerator;
            long denominator = left.m_Denominator * right.m_Denominator;

            return new Fraction(numerator, denominator);
          }
        }
        catch (Exception e)
        {
          throw new FractionException("Multiply error", e);
        }
      }

      /// <summary>
      /// Returns the modulus (remainder after dividing) two Fractions
      /// </summary>
      /// <param name="left">A Fraction</param>
      /// <param name="right">Another Fraction</param>
      /// <returns>Modulus of the Fractions. Returns NaN if either Fraction is a NaN.</returns>
      /// <exception cref="FractionException">Will throw if an overflow occurs. Does a cross-reduce to 
      /// insure only the unavoidable overflows occur.</exception>
      private static Fraction Modulus(Fraction left, Fraction right)
      {
        if (left.IsNaN() || right.IsNaN())
          return NaN;

        try
        {
          checked
          {
            // this will discard any fractional places...
            Int64 quotient = (Int64)(left / right);
            Fraction whole = new Fraction(quotient * right.m_Numerator, right.m_Denominator);
            return left - whole;
          }
        }
        catch (Exception e)
        {
          throw new FractionException("Modulus error", e);
        }
      }

      /// <summary>
      /// Computes the greatest common divisor for two values
      /// </summary>
      /// <param name="left">One value</param>
      /// <param name="right">Another value</param>
      /// <returns>The greatest common divisor of the two values</returns>
      /// <example>(6, 9) returns 3 and (11, 4) returns 1</example>
      private static long GCD(long left, long right)
      {
        // take absolute values
        if (left < 0)
          left = - left;

        if (right < 0)
          right = - right;
              
        // if we're dealing with any zero or one, the GCD is 1
        if (left < 2 || right < 2)
          return 1;

        do
        {
          if (left < right)
          {
            long temp = left;  // swap the two operands
            left = right;
            right = temp;
          }

          left %= right;
        } while (left != 0);

        return right;
      }
      #endregion

      #region Indeterminate helpers
      /// <summary>
      /// Gives the culture-related representation of the indeterminate types NaN, PositiveInfinity
      /// and NegativeInfinity
      /// </summary>
      /// <param name="numerator">The value in the numerator</param>
      /// <returns>The culture-specific string representation of the implied value</returns>
      /// <remarks>Only the sign and zero/non-zero information is relevant.</remarks>
      private static string IndeterminateTypeName(long numerator)
      {
        // could also be NumberFormatInfo.InvariantInfo
        System.Globalization.NumberFormatInfo info = NumberFormatInfo.CurrentInfo;

        switch (NormalizeIndeterminate(numerator))
        {
          case Indeterminates.PositiveInfinity:
            return info.PositiveInfinitySymbol;

          case Indeterminates.NegativeInfinity:
            return info.NegativeInfinitySymbol;

          default:    // if this happens, something VERY wrong is going on...
          case Indeterminates.NaN:
            return info.NaNSymbol;
        }
      }

      /// <summary>
      /// Gives the normalize representation of the indeterminate types NaN, PositiveInfinity
      /// and NegativeInfinity
      /// </summary>
      /// <param name="numerator">The value in the numerator</param>
      /// <returns>The normalized version of the indeterminate type</returns>
      /// <remarks>Only the sign and zero/non-zero information is relevant.</remarks>
      private static Indeterminates NormalizeIndeterminate(long numerator)
      {
        switch (Math.Sign(numerator))
        {
          case 1:
            return Indeterminates.PositiveInfinity;

          case -1:
            return Indeterminates.NegativeInfinity;

          default:    // if this happens, your Math.Sign function is BROKEN!
          case 0:
            return Indeterminates.NaN;
        }
      }

      // These are used to represent the indeterminate with a Denominator of zero
      private enum Indeterminates
      {
        NaN = 0
        , PositiveInfinity = 1
        , NegativeInfinity = -1
      }
      #endregion

      #region Member variables
      private long m_Numerator;
      private long m_Denominator;
      #endregion
      #endregion
    }   //end class Fraction

    /// <summary>
    /// Exception class for Fraction, derived from System.Exception
    /// </summary>
    public class FractionException : Exception
    {
      /// <summary>
      /// Constructs a FractionException
      /// </summary>
      /// <param name="Message">String associated with the error message</param>
      /// <param name="InnerException">Actual inner exception caught</param>
      public FractionException(string Message, Exception InnerException) : base(Message, InnerException)
      {
      }
    }   //end class FractionException
  }   //end namespace Mehroz