Algorithm for Simplifying Decimal to Fractions

algorithm to convert decimal to fraction expression

Have you looked into continued fractions? They give very good approximations of numbers.

How to convert decimal to fractions?

You should find the greatest common divisor of the resulted numbers and divide the numerator and denominator by it.

Here is one way to do it:

public class Rational {

    private int num, denom;

    public Rational(double d) {
        String s = String.valueOf(d);
        int digitsDec = s.length() - 1 - s.indexOf('.');
        int denom = 1;
        for (int i = 0; i < digitsDec; i++) {
            d *= 10;    
            denom *= 10;
        }

        int num = (int) Math.round(d);
        int g = gcd(num, denom);
        this.num = num / g;
        this.denom = denom /g;
    }

    public Rational(int num, int denom) {
        this.num = num;
        this.denom = denom;
    }

    public String toString() {
        return String.valueOf(num) + "/" + String.valueOf(denom);
    }

    public static int gcd(int num, int denom) {
          ....
    }

    public static void main(String[] args) {
        System.out.println(new Rational(1.5));
    }
}

How to convert floats to human-readable fractions?

I have found David Eppstein's find rational approximation to given real number C code to be exactly what you are asking for. Its based on the theory of continued fractions and very fast and fairly compact.

I have used versions of this customized for specific numerator and denominator limits.

/*
** find rational approximation to given real number
** David Eppstein / UC Irvine / 8 Aug 1993
**
** With corrections from Arno Formella, May 2008
**
** usage: a.out r d
**   r is real number to approx
**   d is the maximum denominator allowed
**
** based on the theory of continued fractions
** if x = a1 + 1/(a2 + 1/(a3 + 1/(a4 + ...)))
** then best approximation is found by truncating this series
** (with some adjustments in the last term).
**
** Note the fraction can be recovered as the first column of the matrix
**  ( a1 1 ) ( a2 1 ) ( a3 1 ) ...
**  ( 1  0 ) ( 1  0 ) ( 1  0 )
** Instead of keeping the sequence of continued fraction terms,
** we just keep the last partial product of these matrices.
*/

#include <stdio.h>

main(ac, av)
int ac;
char ** av;
{
    double atof();
    int atoi();
    void exit();

    long m[2][2];
    double x, startx;
    long maxden;
    long ai;

    /* read command line arguments */
    if (ac != 3) {
        fprintf(stderr, "usage: %s r d\n",av[0]);  // AF: argument missing
        exit(1);
    }
    startx = x = atof(av[1]);
    maxden = atoi(av[2]);

    /* initialize matrix */
    m[0][0] = m[1][1] = 1;
    m[0][1] = m[1][0] = 0;

    /* loop finding terms until denom gets too big */
    while (m[1][0] *  ( ai = (long)x ) + m[1][1] <= maxden) {
        long t;
        t = m[0][0] * ai + m[0][1];
        m[0][1] = m[0][0];
        m[0][0] = t;
        t = m[1][0] * ai + m[1][1];
        m[1][1] = m[1][0];
        m[1][0] = t;
        if(x==(double)ai) break;     // AF: division by zero
        x = 1/(x - (double) ai);
        if(x>(double)0x7FFFFFFF) break;  // AF: representation failure
    } 

    /* now remaining x is between 0 and 1/ai */
    /* approx as either 0 or 1/m where m is max that will fit in maxden */
    /* first try zero */
    printf("%ld/%ld, error = %e\n", m[0][0], m[1][0],
           startx - ((double) m[0][0] / (double) m[1][0]));

    /* now try other possibility */
    ai = (maxden - m[1][1]) / m[1][0];
    m[0][0] = m[0][0] * ai + m[0][1];
    m[1][0] = m[1][0] * ai + m[1][1];
    printf("%ld/%ld, error = %e\n", m[0][0], m[1][0],
           startx - ((double) m[0][0] / (double) m[1][0]));
}

Get the simple fraction of decimal number c#

Here is sample code. Can get stuck in infinite loop (let OP solve this issue). I rounded to number of decimal places in input :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml;
using System.Xml.Linq;
using System.Data;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] numbers = { "1", "16", "0.125", ".30769231" };

            foreach (string number in numbers)
            {
                int numerator = 1;
                string strNumerator = "";
                int denominator = 1;
                string strDenominator = "";

                Boolean done = false;

                if (!number.Contains("."))
                {
                    strNumerator = number;
                    strDenominator = "1";
                    done = true;
                }
                else
                {
                    int numberDecimalPlaces = number.Substring(number.IndexOf(".")).Length - 1;
                    string tempStr = number;
                    if (number.StartsWith(".")) tempStr = "0" + tempStr;
                    double value = double.Parse(number);

                    while(!done)
                    {
                        while (true)
                        {
                            double newTemp = numerator / (double)denominator;
                            string newTempStr = newTemp.ToString("F" + numberDecimalPlaces.ToString());
                            if (newTempStr == tempStr)
                            {
                                strNumerator = numerator.ToString();
                                strDenominator = denominator.ToString();
                                done = true;
                                break;
                            }
                            denominator++;
                            if (newTemp <= value)
                            {
                                numerator += 1;
                                denominator = numerator + 1;
                                break;
                            }

                        }

                    }

                }
                Console.WriteLine("Results for : '{0}', numerator = '{1}', denominator = '{2}'", number, strNumerator, strDenominator);
            }
            Console.ReadLine();
        }
    }

}

---

Related Topics