javascript - How to simplify a decimal into the smallest possible fraction?

Question

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

Answer 1

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

If x is a rational number, the process stops at some point with h_n/k_n == x. If x is not a rational number, the sequence h_n/k_n, 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.