javascript - 如何将小数简化为最小的分数？

Question

例如，如果我的函数名为getlowestfraction()，这就是我期望的功能:

getlowestfraction(0.5) // returns 1, 2 or something along the lines of that

另一个例子:

getlowestfraction(0.125) // returns 1, 8 or something along the lines of that

Answer 1

使用Continued Fractions可以有效地创建分数(hn / kn)的(有限或无限)序列，它们是给定实数x的任意良好近似值。

如果x是有理数，则过程在hn / kn == x的某个点处停止。如果x不是有理数，则序列hn / kn，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。