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

You could keep multiplying by ten until you have integer values for your numerator and denominator, then use the answers from this question to reduce the fraction to its simplest terms.

Answer 2

Try this program instead:

function toFrac(number) {
    var fractional = number % 1;

    if (fractional) {
        var real = number - fractional;
        var exponent = String(fractional).length - 2;
        var denominator = Math.pow(10, exponent);
        var mantissa = fractional * denominator;
        var numerator = real * denominator + mantissa;
        var gcd = GCD(numerator, denominator);
        denominator /= gcd;
        numerator /= gcd;
        return [numerator, denominator];
    } else return [number, 1];
}

function gcd(numerator, denominator) {
    do {
        var modulus = numerator % denominator;
        numerator = denominator;
        denominator = modulus;
    } while (modulus);

    return numerator;
}

Then you may use it as follows:

var start = new Date;
var PI = toFrac(Math.PI);
var end = new Date;

alert(PI);
alert(PI[0] / PI[1]);
alert(end - start + " ms");

You can see the demo here: http://jsfiddle.net/MZaK9/1/

Answer 3

Was just fiddling around with code, and got the answer myself:

function getlowestfraction (num) {
  var i = 1;
  var mynum = num;
  var retnum = 0;
  while (true) {
    if (mynum * i % 1 == 0) {
      retnum = mynum * i;
      break;
    }
    // For exceptions, tuned down MAX value a bit
    if (i > 9000000000000000) {
      return false;
    }
    i++;
  }
  return retnum + ", " + i;
}

In case anybody needed it.

P.S: I'm not trying to display my expertise or range of knowledge. I actually did spend a long time in JSFiddle trying to figure this out (well not a really long time anyway).

Answer 4

Suppose the number is x = 0 . ( a_1 a_2 ... a_k ) ( a_1 a_2 ... a_k ) .... for simplicity (keep in mind that the first few digits may not fit the repeating pattern, and that we need a way to figure out what k is). If b is the base, then

b ^ k * x - x = ( b ^ k - 1 ) * x

on one hand, but

b ^ k * x - x = ( a_1 a_2 ... a_k )

(exact, ie this is an integer) on the other hand.

So

x = ( a_1 ... a_k ) / ( b ^ k - 1 )

Now you can use Euclid's algorithm to get the gcd and divide it out to get the reduced fraction.

You would still have to figure out how to determine the repeating sequence. There should be an answer to that question. EDIT - one answer: it's the length of \1 if there's a match to the pattern /([0-9]+)\1+$/ (you might want to throw out the last digit before matching bc of rounding). If there's no match, then there's no better "answer" than the "trivial" representation" (x*base^precision/base^precision).

N.B. This answer makes some assumptions on what you expect of an answer, maybe not right for your needs. But it's the "textbook" way of getting reproducing the fraction from a repeating decimal representation - see e.g. here

Answer 5

A very old but a gold question which at the same time an overlooked one. So i will go and mark this popular one as a duplicate with hopes that new people end up at the correct place.

The accepted answer of this question is a gem of the internet. No library that i am aware of uses this magnificient technique and ends up with not wrong but silly rationals. Having said that, the accepted answer is not totally correct due to several issues like;

1. What exactly is happening there?
2. Why it still returns '140316103787451/7931944815571' instead of '1769/100' when the input is 17.69?
3. How do you decide when to stop the while loop?

Now the most important question is, what's happening there and howcome this algorithm is so very efficient.

We must know that any number can also be expressed as a continuous fraction. Say you are given 0.5. You can express it like

     1
0 + ___  // the 0 here is in fact Math.floor(0.5)
     2   // the 2 here is in fact Math.floor(1/0.5)

So say you are given 2.175 then you end up with

           1
2 + _______________  // the 2 here is in fact Math.floor(2.175)
             1
    5 + ___________  // the 5 here is in fact Math.floor(1/0.175 = 5.714285714285714)
               1
        1 + _______  // the 1 here is in fact Math.floor(1/0.714285714285714 = 1.4)
                 1
            2 + ___  // the 2 here is in fact Math.floor(1/0.4 = 2.5)
                 2   // the 2 here is in fact Math.floor(1/0.5)

We now have our continued fraction coefficients like [2;5,1,2,2] for 2.175. However the beauty of this algorithm lies behind how it calculates the approximation at once when we calculate the next continued fraction constant without requiring any further calculations. At this very moment we can compare the currently reached result with the given value and decide to stop or iterate once more.

So far so good however it still doesn't make sense right? Let us go with another solid example. Input value is 3.686635944700461. Now we are going to approach this from Infinity and very quickly converge to the result. So our first rational is 1/0 aka Infinity. We denote this as a fraction with a numerator p as 1 and denominator q as 0 aka 1/0. The previous approximation would be p_/q_ for the next stage. Let us make it 0 to start with. So p_ is 0 and q_ is 1.

The important part is, once we know the two previous approximations, (p, q, p_ and q_) we can then calculate the next coefficient m and also the next p and q to compare with the input. Calculating the coefficient m is as simple as Math.floor(x_) whereas x_ is reciprocal of the next floating part. The next approximation p/q would then be (m * p + p_)/(m * q + q_) and the next p_/q_ would be the previous p/q. (Theorem 2.4 @ this paper)

Now given above information any decent programmer can easily resolve the following snippet. For curious, 3.686635944700461 is 800/217 and gets calculated in just 5 iterations by the below code.

function toRational(x){
  var m  = Math.floor(x),
      x_ = 1/(x-m),
      p_ = 1,
      q_ = 0,
      p  = m,
      q  = 1;
  if (x === m) return {n:p,d:q};
  while (Math.abs(x - p/q) > Number.EPSILON){
    m  = Math.floor(x_);
    x_ = 1/(x_-m);
    [p_, q_, p, q] = [p, q, m*p+p_, m*q+q_];
  }
  return isNaN(x) ? NaN : {n:p,d:q};
}

Under practical considerations it would be ideal to store the coefficients in the fraction object as well so that in future you may use them to perform CFA (Continuous Fraction Arithmetics) among rationals. This way you may avoid huge integers and possible BigInt usage by staying in the CF domain to perform invertion, negation, addition and multiplication operations. Sadly, CFA is a very overlooked topic but it helps us to avoid double precision errors when doing cascaded arithmetic operations on the rational type values.