5

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
Lucas
  • 16,930
  • 31
  • 110
  • 182

6 Answers6

21

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.
Martin R
  • 529,903
  • 94
  • 1,240
  • 1,382
  • This is a good answer. A good choice of eps can be determined from the length of the period of repetition - e.g. if the period is k digits, a good choice of eps is base^(-k) (since an upper bound for the denominator is -1 + base^k). Anything larger and the algorithm might overcompensate (after all, the number is inherently stored as a not-quite-correct rational number, which for all the machine knows could be a "perfect" representation). Your 1/7 example illustrates this perfectly. If eps is too big it'll accept an incorrect answer (e.g. if eps = 1 the nearest integer will be accepted). – amomin Dec 23 '12 at 21:07
  • @amomin: Thank you! But one advantage of this method is that is does not assume any period of repetition. For example, what would the period length be for (the machine approximation of) Pi? I think it is better to think of "precision". If have chosen eps=1E-15 as example because that (roughly) corresponds to the number of significant digits of a double precision number. But if the number is some user input with e.g. 6 digits after the decimal point, then eps=1E-6 would be appropriate. Anyway, thanks for the feedback. – Martin R Dec 23 '12 at 21:26
  • Great point! This also points out an ambiguity in the problem (at least I think so). If you really want the "right" rational representation whenever possible (and to gather evidence for/against the number being rational), you shouldn't fix epsilon. But if you concern is about getting *some* answer, even if the number is irrational, then this is the definitely way to go. I was thinking more along the former lines. – amomin Dec 23 '12 at 21:58
  • Brilliant but still has some problems. – Redu Feb 17 '22 at 20:21
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.

Community
  • 1
  • 1
Matthew Strawbridge
  • 19,940
  • 10
  • 72
  • 93
  • 1
    You should probably multiply by 2 instead, knowing that JavaScript numbers are binary double-precision floating-point numbers. – Aadit M Shah Dec 23 '12 at 02:17
  • what about 0.3333...? (or for a binary example .010101010...) - actually, i'm confused, i thought the whole point was that you don't know the num/denum beforehand. – amomin Dec 23 '12 at 07:09
  • @amomin The original numerator is the floating-point number and the original denominator is 1. Then you multiply both the numerator and denominator repeatedly until the numerator is an integer. – Matthew Strawbridge Dec 23 '12 at 08:35
  • For numbers that are not exactly representable as a binary float, you will end up with a close but different fraction. – Matthew Strawbridge Dec 23 '12 at 08:38
  • @AaditMShah Thinking about it, perhaps 10 is better after all so that 0.1 comes out as 1/10. So 10 is better for floats entered by people; 2 is better for floats entered by machine (e.g. converting a random float to a random fraction) – Matthew Strawbridge Dec 23 '12 at 08:42
  • @MatthewStrawbridge But you're only going to get an integer in the numerator (let's even forget about machine problems) if you multiply eventually by the a number that is divisible by the denominator - which we don't know to begin with. You can't just keep multiplying by 10 and expect to end up with an integer, e.g. if you have 1/7 or 1/3 (or and denominator that has a factor which isn't 2 or 5). (stricly speaking, of course you do *eventually*, but you're just getting the trivial solution (x*10^precision/10^precision) - I assume we want to do better than that...) – amomin Dec 23 '12 at 20:54
  • @amomin Yes, you might end up with x*10^precision/10^precision as the worst case, then you *reduce that to its simplest terms* as I said in my answer. – Matthew Strawbridge Dec 23 '12 at 21:25
1

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/

Aadit M Shah
  • 72,912
  • 30
  • 168
  • 299
1

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.

Redu
  • 25,060
  • 6
  • 56
  • 76
0

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).

Lucas
  • 16,930
  • 31
  • 110
  • 182
  • Won't you get an infinite loop if `num` is not exactly 1/n for some integer n? For example, what happens with `getlowestfraction(0.6)`? – Matthew Strawbridge Dec 22 '12 at 10:59
  • This is clever! +1 for both the question and the answer. –  Dec 22 '12 at 11:03
  • Just wanted to let you know that this function is really slow: http://jsfiddle.net/Y5kzJ/1/ There must be a better way to do it. Give me some time and I'll figure it out. – Aadit M Shah Dec 22 '12 at 11:04
  • You may already be, but I hope you're conscious of the dangers of using floating point numbers in this kind of context. `getlowestfraction(0.3)` correctly returns `3, 10`. `getlowestfraction(0.1+0.2)` hangs my browser. – Mark Amery Dec 22 '12 at 11:10
  • @AaditMShah Sorry, you're right. I hadn't realised it was trying each denominator in turn. It seems to struggle with `getlowestfraction(0.101010101010101)` -- at least, I didn't wait for it to finish ;-) – Matthew Strawbridge Dec 22 '12 at 11:11
  • @MatthewStrawbridge Added something just in case for infinite loops. – Lucas Dec 22 '12 at 11:29
  • @think123 Yeah, 9 quadrillion iterations should be enough for anyone ;-) – Matthew Strawbridge Dec 22 '12 at 13:56
  • @MatthewStrawbridge (maths nerd, bothered to count zeroes) no offence. – Lucas Dec 22 '12 at 21:57
0

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

amomin
  • 396
  • 1
  • 6
  • 14