## 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 *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*converges to

_{n}/k_{n}, n = 0, 1, 2, …*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)