How to simplify a decimal into the smallest possible fraction?

by

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 + "https://stackoverflow.com/" + 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.

More Related Contents:

  1. How to find the least common multiple of a range of numbers?
  2. How to receive and maintain values in functions (javascript)
  3. Set a default parameter value for a JavaScript function
  4. What is the scope of variables in JavaScript?
  5. Javascript call() & apply() vs bind()?
  6. JavaScript plus sign in front of function expression
  7. jQuery 1.9 .live() is not a function
  8. Calling a function every 60 seconds
  9. JavaScript % (modulo) gives a negative result for negative numbers
  10. Are “(function ( ) { } ) ( )” and “(function ( ) { } ( ) )” functionally equal in JavaScript? [duplicate]
  11. How to add an object to an array
  12. Javascript: formatting a rounded number to N decimals
  13. Is it possible to get all arguments of a function as single object inside that function?
  14. Add two functions to window.onload
  15. The invocation context (this) of the forEach function call
  16. Javascript functions like “var foo = function bar() …”?
  17. Why in JavaScript both “Object instanceof Function” and “Function instanceof Object” return true?
  18. What happens if I call a JS method with more parameters than it is defined to accept?
  19. Where should functions in function components go?
  20. Why most JavaScript native functions are slower than their naive implementations?
  21. onsubmit multiple javascript functions
  22. Why can’t I set a JavaScript function’s name property?
  23. How to create javascript delay function [duplicate]
  24. Javascript: Creating Functions in a For Loop
  25. Get values from an object in JavaScript [duplicate]
  26. How does the (function() {})() construct work and why do people use it?
  27. difference between parseInt() and parseFloat() [duplicate]
  28. Javascript: PI (π) Calculator
  29. Passing a function with arguments as an argument?
  30. javascript click event handler fires without clicking

Leave a Comment