алгоритм для преобразования десятичных чисел дроби выражение

Question

предположив У меня есть десятичное как

0.30000000000000027 

Что бы лучший алгоритм, чтобы знать то же самое число выражается в виде дроби Так, при определенных x найти y, что удовлетворяет x=1/y в с или Haskell

Я думал

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

Вы смотрели в continued fractions? Они дают очень хорошие аппроксимации чисел.

Answer 2

Voila (преобразует почти правильно к нормальным ФВ):

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 3

Не знаю Haskell, здесь в псевдокоде:

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