c - 将小数转换为分数表达式的算法

Question

假设我有一个小数

0.30000000000000027

知道用分数表示的相同数字的最佳算法是什么所以给定满足c或haskell的某些x发现yx=1/y

我刚在想

 1/3> 0.30 >1/4

迭代左侧和右侧，直到其中一个收敛并>变为= 第一次迭代看起来像

1/1  >  0.30000000000000027  > 1/somethinghere
1/2  >  0.30000000000000027  > 1/increase or decrease this 
1/3  >  0.30000000000000027 ...

我想澄清一下，我可以很容易地做到

0.30000000000000027  =  30000000000000027/  10^17

但我想做

0.30000000000000027 = 1/x

在 c 或 haskell 中

Answer 1

瞧（几乎正确地转换为正常分数）：

int gcd(int a, int b)
{
    if (a == 0) return b;
    if (b == 0) return a;

    if (a > b)
        return gcd(b, a % b);
    else
        return gcd(a, b % a);
}

struct frac {
    int num;
    int denom;
};

struct frac to_frac(double x, int precision)
{
    int denom = 1;
    for (int i = 0; i < precision; i++) {
        denom *= 10;
    }

    int num = x * denom + 0.5; // hack: round if imprecise
    int gcdiv = gcd(num, denom);

    struct frac f;
    f.num = num / gcdiv;
    f.denom = denom / gcdiv;

    return f;
}

Answer 2

你研究过连分数吗？它们给出了非常好的数字近似值。

Answer 3

不知道haskell，这里是伪代码：

raw_denom = 1/x;
print "1/" floor(raw_denom) " >= " x " >= 1/" ceil(raw_denom)