Decimal to Fraction

Question

I am working on a system that needs to accept and display complex fractions. The code for accepting fractions and turning them in to a double works, but when I want to display that value, I need to convert back to a fractional representation.

EDIT: I have fixed the overflow problem, but that didnt solve fractions like 1/3 or 5/6. SO I have devised a very hacky way to do this. I have code which generates the decimal representation of every fraction 0->64 over 1->64, and saves the most simplified form. This way, I can iterate through the list and find the closest fraction, and simply display that. Will post code once I have some.

I have code now that works for the vast majority of numbers, but occasionally I will get a tiny fraction like 1/321. This gets converted to a double, but cannot be converted back, because in my approach, the numerator causes an integer overflow.

Here is my code, I'm wondering if there is a better approach, or if there is someway to safely convert these to longs without losing the precision needed for a correct result:

public static String DecimalToFraction(double dec)
    {
        string str = dec.ToString();
        if (str.Contains('.'))
        {
            String[] parts = str.Split('.');
            long whole = long.Parse(parts[0]);
            long numerator = long.Parse(parts[1]);
            long denominator = (long)Math.Pow(10, parts[1].Length);
            long divisor = GCD(numerator, denominator);
            long num = numerator / divisor;
            long den = denominator / divisor;

            String fraction = num + "/" + den;
            if (whole > 0)
            {
                return whole + " " + fraction;
            }
            else
            {
                return fraction;
            }
        }
        else
        {
            return str;
        }
    }

    public static long GCD(long a, long b)
    {
        return b == 0 ? a : GCD(b, a % b);
    }

Answer 1

Please check these 2 methods:

/// <summary>
    /// Converts Decimals into Fractions.
    /// </summary>
    /// <param name="value">Decimal value</param>
    /// <returns>Fraction in string type</returns>
    public string DecimalToFraction(double value)
    {
        string result;
        double numerator, realValue = value;
        int num, den, decimals, length;
        num = (int)value;
        value = value - num;
        value = Math.Round(value, 5);
        length = value.ToString().Length;
        decimals = length - 2;
        numerator = value;
        for (int i = 0; i < decimals; i++)
        {
            if (realValue < 1)
            {
                numerator = numerator * 10;
            }
            else
            {
                realValue = realValue * 10;
                numerator = realValue;
            }
        }
        den = length - 2;
        string ten = "1";
        for (int i = 0; i < den; i++)
        {
            ten = ten + "0";
        }
        den = int.Parse(ten);
        num = (int)numerator;
        result = SimplifiedFractions(num, den);
        return result;
    }

    /// <summary>
    /// Converts Fractions into Simplest form.
    /// </summary>
    /// <param name="num">Numerator</param>
    /// <param name="den">Denominator</param>
    /// <returns>Simplest Fractions in string type</returns>
    string SimplifiedFractions(int num, int den)
    {
        int remNum, remDen, counter;
        if (num > den)
        {
            counter = den;
        }
        else
        {
            counter = num;
        }
        for (int i = 2; i <= counter; i++)
        {
            remNum = num % i;
            if (remNum == 0)
            {
                remDen = den % i;
                if (remDen == 0)
                {
                    num = num / i;
                    den = den / i;
                    i--;
                }
            }
        }
        return num.ToString() + "/" + den.ToString();
    }
}

Answer 2

Recently I had to code a similar scenario. In my case, converting from decimal to rational number had to be a little more mathematically correct so I ended up implementing a Continued Fraction algorithm.

Although it is tailored made to my concrete implementation of RationalNumber, you should get the idea. It's a relatively simple algorithm that works reasonably well for any rational number approximation. Note that the implementation will give you the closest approximation with the required precision.

/// <summary>
/// Represents a rational number with 64-bit signed integer numerator and denominator.
/// </summary>
[Serializable]
public struct RationalNumber : IComparable, IFormattable, IConvertible, IComparable<RationalNumber>, IEquatable<RationalNumber>
{
     private const int MAXITERATIONCOUNT = 20;

     public RationalNumber(long number) {...}
     public RationalNumber(long numerator, long denominator) {...}
     public RationalNumber(RationalNumber numerator, RationalNumer denominator) {...}

     ...
     /// <summary>
     /// Defines an implicit conversion of a 64-bit signed integer to a rational number.
     /// </summary>
     /// <param name="value">The value to convert to a rational number.</param>
     /// <returns>A rational number that contains the value of the value parameter as its numerator and 1 as its denominator.</returns>
     public static implicit operator RationalNumber(long value)
     {
         return new RationalNumber(value);
     }

     /// <summary>
     /// Defines an explicit conversion of a rational number to a double-precision floating-point number.
     /// </summary>
     /// <param name="value">The value to convert to a double-precision floating-point number.</param>
     /// <returns>A double-precision floating-point number that contains the resulting value of dividing the rational number's numerator by it's denominator.</returns>
     public static explicit operator double(RationalNumber value)
     {
         return (double)value.numerator / value.Denominator;
     }

     ...
     /// <summary>
     /// Adds two rational numbers.
     /// </summary>
     /// <param name="left">The first value to add.</param>
     /// <param name="right">The second value to add.</param>
     /// <returns>The sum of left and right.</returns>
     public static RationalNumber operator +(RationalNumber left, RationalNumber right)
     {
         //First we try directly adding in a checked context. If an overflow occurs we use the least common multiple and return the result. If it overflows again, it
         //will be up to the consumer to decide what he will do with it.
         //Cost penalty should be minimal as adding numbers that cause an overflow should be very rare.

         RationalNumber result;

         try
         {
             long numerator = checked(left.numerator * right.Denominator + right.numerator * left.Denominator);
             long denominator = checked(left.Denominator * right.Denominator);
             result = new RationalNumber(numerator,denominator);
         }
         catch (OverflowException)
         {
             long lcm = RationalNumber.getLeastCommonMultiple(left.Denominator, right.Denominator);
             result = new RationalNumber(left.numerator * (lcm / left.Denominator) + right.numerator * (lcm / right.Denominator), lcm);
         }

         return result;
     }

     private static long getGreatestCommonDivisor(long i1, long i2)
     {
        Debug.Assert(i1 != 0 || i2 != 0, "Whoops!. Both arguments are 0, this should not happen.");

        //Division based algorithm
        long i = Math.Abs(i1);
        long j = Math.Abs(i2);
        long t;

        while (j != 0)
        {
            t = j;
            j = i % j;
            i = t;
        }

        return i;
    }

    private static long getLeastCommonMultiple(long i1, long i2)
    {
        if (i1 == 0 && i2 == 0)
            return 0;

        long lcm = i1 / getGreatestCommonDivisor(i1, i2) * i2;
        return lcm < 0 ? -lcm : lcm;
     }
     ...

     /// <summary>
     /// Returns the nearest rational number approximation to a double-precision floating-point number with a specified precision.
     /// </summary>
     /// <param name="target">Target value of the approximation.</param>
     /// <param name="precision">Minimum precision of the approximation.</param>
     /// <returns>Nearest rational number with, at least, the required precision.</returns>
     /// <exception cref="System.ArgumentException">Can not find a rational number approximation with specified precision.</exception>
     /// <exception cref="System.OverflowException">target is larger than Mathematics.RationalNumber.MaxValue or smaller than Mathematics.RationalNumber.MinValue.</exception>
     /// <remarks>It is important to clarify that the method returns the first rational number found that complies with the specified precision. 
     /// The method is not required to return an exact rational number approximation even if such number exists.
     /// The returned rational number will always be in coprime form.</remarks>
     public static RationalNumber GetNearestRationalNumber(double target, double precision)
     {
         //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 evaluates a Rational approximation for increasing algorithm depths until precision criteria is met or maximum depth is reached (MAXITERATIONCOUNT)
         //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.

         RationalNumber nearestRational = RationalNumber.zero;
         int steps = 0;

         while (Math.Abs(target - (double)nearestRational) > precision)
         {
             if (steps > MAXITERATIONCOUNT)
                 throw new ArgumentException(Strings.RationalMaximumIterationsExceptionMessage, "precision");

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

         return nearestRational;
     }

    private static RationalNumber getNearestRationalNumber(double number, int currentStep, int maximumSteps)
    {
        long integerPart;
        integerPart = checked((long)number);
        double fractionalPart = number - integerPart;

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

        return new RationalNumber(integerPart);
    }     
}

UPDATE: Whoops, forgot to include the operator + code. Fixed it.

Answer 3

Keep the number as a fraction:

struct Fraction
{
     private int _numerator;
     private int _denominator;

     public int Numerator { get { return _numerator; } }
     public int Denominator { get { return _denominator; } }
     public double Value { get { return ((double) Numerator)/Denominator; } }

     public Fraction( int n, int d )
     {
         // move negative to numerator.
         if( d < 0 )
         {
            _numerator = -n;
            _denominator = -d;
         }
         else if( d > 0 )
         {
            _numerator = n;
            _denominator = d;
         }
         else
            throw new NumberFormatException( "Denominator cannot be 0" );
    }



     public void ToString()
     {
         string ret = "";
         int whole = Numerator / Denominator;
         if( whole != 0 )
             ret += whole + " ";
         ret += Math.Abs(Numerator % Denominator) + "/" + Denominator;
         return ret;
     }
} 

Answer 4

You could use BigRational, which Microsoft released under their BCL project on codeplex. It supports arbitrarily large rational numbers, and actually stores it internally as a ratio. The nice thing is that you can treat it largely as a normal numeric type, since all of the operators are overloaded for you.

Interestingly, it lacks a way to print the number as a decimal. I wrote some code that did this, though, in a previous answer of mine. However, there are no guarantees on its performance or quality (I barely remember writing it).