小数から無理数の近似

Question

浮動小数点10進法から有理数分数近似（例：0.333 - > 1/3）のアルゴリズムを実装しましたが、今は条件を満たす不合理な数を見つける方法があります。たとえば、入力が0.282842712474の場合、私のアルゴリズムが生成する結果はsqrt（2）/ 5で、431827/1526739ではないとします。唯一の条件は、結果の最初の桁（浮動小数点に変換されたもの）が入力の桁でなければならないということです。残りは重要ではありません。前もって感謝します！

Answer 1

私は解を思いつきました。与えられた分母と指名子の集合から、与えられた数の最良の近似が見つけられました。この解決策は見つけよりもセットは、N個の要素を有する場合
=被平方根< = 100000
= root_index < = 20

：このセットにより作成することができるすべての数値を含むことができる。例えば

O（N log N）における最良の近似。

このソリューションでは、Xは分母とYノミネータを表します。

1. ソートセットからの各数Xの設定
2. から番号：使用
   バイナリ検索最小YようにY/X> = input_number
   コンペアY/X input_numberの現在最良の近似と

私は抵抗することができませんでしたし、私はそれを実装：

#include <cstdio> 
#include <vector> 
#include <algorithm> 
#include <cmath> 
using namespace std; 

struct Number { 
    // number value 
    double value; 

    // number representation 
    int root_index; 
    int radicand; 

    Number(){} 
    Number(double value, int root_index, int radicand) 
    : value(value), root_index(root_index), radicand(radicand) {} 

    bool operator < (const Number& rhs) const { 
    // in case of equal numbers, i want smaller radicand first 
    if (fabs(value - rhs.value) < 1e-12) return radicand < rhs.radicand; 
    return value < rhs.value; 
    } 

    void print() const { 
    if (value - (int)value < 1e-12) printf("%.0f", value); 
    else printf("sqrt_%d(%d)",root_index, radicand); 
    } 
}; 

std::vector<Number> numbers; 
double best_result = 1e100; 
Number best_numerator; 
Number best_denominator; 

double input; 

void compare_approximpation(const Number& numerator, const Number& denominator) { 
    double value = numerator.value/denominator.value; 

    if (fabs(value - input) < fabs(best_result - input)) { 
     best_result = value; 
     best_numerator = numerator; 
     best_denominator = denominator; 
    } 
} 

int main() { 

    const int NUMBER_LIMIT = 100000; 
    const int ROOT_LIMIT = 20; 

    // only numbers created by this loops will be used 
    // as numerator and denominator 
    for(int i=1; i<=ROOT_LIMIT; i++) { 
    for(int j=1; j<=NUMBER_LIMIT; j++) { 
     double value = pow(j, 1.0 /i); 
     numbers.push_back(Number(value, i, j)); 
    } 
    } 

    sort(numbers.begin(), numbers.end()); 

    scanf("%lf",&input); 

    int numerator_index = 0; 

    for(int denominator_index=0; denominator_index<numbers.size(); denominator_index++) { 
    // you were interested only in integral denominators 
    if (numbers[denominator_index].root_index == 1) { 
     // i use simple sweeping technique instead of binary search (its faster) 
     while(numerator_index < numbers.size() && numbers[numerator_index].root_index && 
    numbers[numerator_index].value/numbers[denominator_index].value <= input) { 
     numerator_index++; 
     } 

     // comparing approximations 
     compare_approximpation(numbers[numerator_index], numbers[denominator_index]); 
     if (numerator_index > 0) { 
    compare_approximpation(numbers[numerator_index - 1], numbers[denominator_index]); 
     } 
    } 
    } 

    printf("Best approximation %.12lf = ", best_numerator.value/best_denominator.value); 
    best_numerator.print(); 
    printf("/"); 
    best_denominator.print(); 
    printf("\n"); 
}