Geek Answers Handbook

How to simplify the decimal fraction to the smallest fraction possible?

For example, if my function was called getlowestfraction(), this is what I expect from it:

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
+1
source share
5 answers

Using Continued fractions , it is possible to efficiently create (finite or infinite) a sequence of fractions h n / k n that are arbitrary good approximations to a given real number x.

x - , h n/k n == x. x , h n/k n, n = 0, 1, 2,... x.

( ), " " .

JavaScript ( C), JavaScript. , , . , , .

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;
}

, eps = 1.0E-15. , . ( while .)

( while):

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)

, 1/3 x = 1.0/3.0. x 10 - 3333333333/10000000000.

:

  • eps = 1.0E-15 getlowestfraction(0.142857) = 142857/1000000.
  • eps = 1.0E-6 getlowestfraction(0.142857) = 1/7.
+6

, , , .

+1

:

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;
}

:

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

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

: http://jsfiddle.net/MZaK9/1/

+1

:

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;
}

- .

P.S: . JSFiddle, (, , ).

0

, x = 0 . ( a_1 a_2 ... a_k ) ( a_1 a_2 ... a_k ) .... (, , k). b - ,

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

,

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

(, .. ), .

,

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

, gcd , .

, . . EDIT - : \1, /([0-9]+)\1+$/ ( bc ). , "", "" "( x/base ^ precision/base ^).

NB This answer gives some assumptions about what you expect from the answer, maybe not suitable for your needs. But this is a “tutorial” way of reproducing a fragment from a repeating decimal representation - see, for example, here

0
source

More articles:


All Articles