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

Question

假设我有一个像这样的小数

0.30000000000000027

知道用分数表示的相同数字的最佳算法是什么 所以给定某些 x 在 c 或 haskell 中找到满足 x=1/y 的 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;
}