如何将小数简化为最小可能的分数？

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

使用连续分数,可以有效地创建(有限或无限)分数序列h _n/k _n,其是对给定实数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.重复乘以x10的幂并取消常见因子会产生类似的结果3333333333/10000000000.

以下是不同精度的示例:

• 随eps = 1.0E-15你而来getlowestfraction(0.142857) = 142857/1000000.
• 随eps = 1.0E-6你而来getlowestfraction(0.142857) = 1/7.