# [SOLVED] How to simplify a decimal into the smallest possible fraction?

## Issue

For example, if my function was called `getlowestfraction()`, this is what I expect it to do:

``````getlowestfraction(0.5) // returns 1, 2 or something along the lines of that
``````

Another example:

``````getlowestfraction(0.125) // returns 1, 8 or something along the lines of that
``````

## Solution

Using Continued Fractions one can efficiently create a (finite or infinite) sequence of fractions hn/kn that are arbitrary good approximations to a given real number x.

If x is a rational number, the process stops at some point with hn/kn == x. If x is not a rational number, the sequence hn/kn, n = 0, 1, 2, … converges to x very quickly.

The continued fraction algorithm produces only reduced fractions (nominator and denominator are relatively prime), and the fractions are in
some sense the “best rational approximations” to a given real number.

I am not a JavaScript person (programming in C normally), but I have tried to implement the algorithm with the following JavaScript function. Please forgive me if there are stupid errors. But I have checked the function and it seems to work correctly.

``````function getlowestfraction(x0) {
var eps = 1.0E-15;
var h, h1, h2, k, k1, k2, a, x;

x = x0;
a = Math.floor(x);
h1 = 1;
k1 = 0;
h = a;
k = 1;

while (x-a > eps*k*k) {
x = 1/(x-a);
a = Math.floor(x);
h2 = h1; h1 = h;
k2 = k1; k1 = k;
h = h2 + a*h1;
k = k2 + a*k1;
}

return h + "/" + k;
}
``````

The loop stops when the rational approximation is exact or has the given precision `eps = 1.0E-15`. Of course, you can adjust the precision to your needs. (The `while` condition is derived from the theory of continued fractions.)

Examples (with the number of iterations of the while-loop):

``````getlowestfraction(0.5)     = 1/2               (1 iteration)
getlowestfraction(0.125)   = 1/8               (1 iteration)
getlowestfraction(0.1+0.2) = 3/10              (2 iterations)
getlowestfraction(1.0/3.0) = 1/3               (1 iteration)
getlowestfraction(Math.PI) = 80143857/25510582 (12 iterations)
``````

Note that this algorithm gives `1/3` as approximation for `x = 1.0/3.0`. Repeated multiplication of `x` by powers of 10 and canceling common factors would give something like `3333333333/10000000000`.

Here is an example of different precisions:

• With `eps = 1.0E-15` you get `getlowestfraction(0.142857) = 142857/1000000`.
• With `eps = 1.0E-6` you get `getlowestfraction(0.142857) = 1/7`.

Answered By – Martin R

Answer Checked By – Dawn Plyler (BugsFixing Volunteer)