Converting Float Decimal to Fraction

Converting float decimal to fraction

Continued fractions can be used to find rational approximations to real numbers that are "best" in a strict sense. Here's a PHP function that finds a rational approximation to a given (positive) floating point number with a relative error less than $tolerance:

<?php
function float2rat($n, $tolerance = 1.e-6) {
    $h1=1; $h2=0;
    $k1=0; $k2=1;
    $b = 1/$n;
    do {
        $b = 1/$b;
        $a = floor($b);
        $aux = $h1; $h1 = $a*$h1+$h2; $h2 = $aux;
        $aux = $k1; $k1 = $a*$k1+$k2; $k2 = $aux;
        $b = $b-$a;
    } while (abs($n-$h1/$k1) > $n*$tolerance);

    return "$h1/$k1";
}

printf("%s\n", float2rat(66.66667)); # 200/3
printf("%s\n", float2rat(sqrt(2)));  # 1393/985
printf("%s\n", float2rat(0.43212));  # 748/1731

I have written more about this algorithm and why it works, and even a JavaScript demo here: https://web.archive.org/web/20180731235708/http://jonisalonen.com/2012/converting-decimal-numbers-to-ratios/

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]));
}

converting floats to fractions

If I understood correctly your problem is not on "how to convert floats to fractions" but yes "how to get a string representation of fraction from arrays of numbers", right?

Actually you can do that in one line:

p = [1,2,3]
q = [3,5,9]

list(map(lambda pair: f"{pair[0]}/{pair[1]}", [(x, y) for x in p for y in q])))

Explaining:

map - receives a function and an iterator, passing each element of the iterator to that function.

[(x, y) for x in p for y in q] - this is a list comprehension, it is generating pairs of numbers "for each x in array p for each y in array q".

lambda pair - this is an anonymous function receiving an argument pair (which we know will be a tuple '(x, y)') and returns the string "x/y" (which is "pair[0]/pair[1]")

Optional procedures

Eliminate zeros in denominator

If you want to avoid impossible fractions (like anything over 0), the list comprehension should be this one:

[(x, y) for x in p for y in q if x != 0]

Eliminate duplicates

Also, if on top of that you want to eliminate duplicate items, just wrap the entire list in a set() operation (sets are iterables with unique elements, and converting a list to a set automatically removes the duplicate elements):

set([(x, y) for x in p for y in q if x != 0])

Eliminate unnecessary duplicate negative signs

The list comprehension is getting a little bigger, but still ok:

set([(x, y) if x>0 or y>0 else (-x,-y) for x in p for y in q if x != 0])
Explaining: if x>0 or y>0, this means that only one of them could be a negative number, so that's ok, return (x,y). If not, that means both of them are negative, so they should be positive, then return (-x,-y).

Testing

The final result of the script is:

p = [1, -1, 0, 2, 3]
q = [3, -5, 9, 0]

print(list(map(lambda pair: f"{pair[0]}/{pair[1]}", set([(x, y) if x>0 or y>0 else (-x,-y) for x in p for y in q if y != 0]))))

# output:
# ['3/-5', '2/-5', '1/5', '1/-5', '0/3', '0/9', '2/3', '2/9', '3/3', '-1/3', '-1/9', '0/5', '3/9', '1/3', '1/9']

How to convert a decimal number into fraction?

You have two options:

Use float.as_integer_ratio():
```
>>> (0.25).as_integer_ratio()
(1, 4)
```
(as of Python 3.6, you can do the same with a decimal.Decimal() object.)

Use the fractions.Fraction() type:

>>> from fractions import Fraction
>>> Fraction(0.25)
Fraction(1, 4)

The latter has a very helpful str() conversion:

>>> str(Fraction(0.25))
'1/4'
>>> print Fraction(0.25)
1/4

Because floating point values can be imprecise, you can end up with 'weird' fractions; limit the denominator to 'simplify' the fraction somewhat, with Fraction.limit_denominator():

>>> Fraction(0.185)
Fraction(3332663724254167, 18014398509481984)
>>> Fraction(0.185).limit_denominator()
Fraction(37, 200)

If you are using Python 2.6 still, then Fraction() doesn't yet support passing in a float directly, but you can combine the two techniques above into:

Fraction(*0.25.as_integer_ratio())

Or you can just use the Fraction.from_float() class method:

Fraction.from_float(0.25)

which essentially does the same thing, e.g. take the integer ratio tuple and pass that in as two separate arguments.

And a small demo with your sample values:

>>> for f in (0.25, 0.5, 1.25, 3.0):
...     print f.as_integer_ratio()
...     print repr(Fraction(f)), Fraction(f)
... 
(1, 4)
Fraction(1, 4) 1/4
(1, 2)
Fraction(1, 2) 1/2
(5, 4)
Fraction(5, 4) 5/4
(3, 1)
Fraction(3, 1) 3

Both the fractions module and the float.as_integer_ratio() method are new in Python 2.6.

Float to Fraction conversion in Python

Yet again it's because floating point numbers aren't stored in base-10 (decimal), but in base-2 (binary).

A number that is finite length in base-10 might be a repeating decimal in base-2. And because floats are a fixed size, that repeating decimal gets truncated, resulting in inaccuracies.

When you use as_integer_ratio for a number that's a repeating decimal in base-2, you will get you a somewhat silly fraction as a result of the slight inaccuracies in the base-10 to base-2 conversion. If you divide those two numbers, the value will be very close to to your original number.

For instance, while 1/10 = 0.1 in base-10 and is not a repeating decimal, it is in fact a repeating decimal in base-2. Just like 1/3 = 0.333... in base-10.

>>> (0.1).as_integer_ratio()
(3602879701896397, 36028797018963968)

If Python's output was exact, you would see this even when you enter just 0.1 in the prompt, by getting something like 1.00000...01 as the output. But Python hides this inaccuracy from you in the general case, leading to confusion.

How do I exactly convert a float to a fraction?

The complicated thing about float-to-fraction conversion is that all floats are already rationals with a power-of-two denominator, but that probably isn't so useful. What you are looking for is "best rational approximation", to find the closest rational to a target float value within some max denominator.

The algorithm (described in the link) has some clever continued fractions math behind it, but not too difficult to put into code. Here is a small C library that implements it:

Header: number_util.h
Source: number_util.c
Unit test: number_util_test.c

Example use:

#include "number_util.h"

int numerator;
int denominator;
RationalApproximation(M_PI, 1000000, NULL, &numerator, &denominator);
printf("%d/%d\n", numerator, denominator); 
// Prints: 3126535/995207 (= 3.14159265...)

This is hopefully straightforward to port or wrap for use in other languages.

Convert a float to an approximate fraction in javascript

You can use a function like this using the https://github.com/peterolson/BigRational.js library:

function rationalize(rational, epsilon) {
    var denominator = 0;
    var numerator;
    var error;

    do {
        denominator++;
        numerator = Math.round((rational.numerator * denominator) / rational.denominator);
        error = Math.abs(rational.minus(numerator / denominator));
    } while (error > epsilon);
    return bigRat(numerator, denominator);
}

It will return a bigRat object. You can check your example with this:

console.log(rationalize(bigRat(3.33333000540733337),0.01));

Converting Float Decimal to Fraction