Aproksymacja od dziesiętnej do irracjonalnej

Question

Zaimplementowałem algorytm dla ułamka dziesiętnego zmiennoprzecinkowego do racjonalnego przybliżenia ułamka (przykład: 0.333 -> 1/3) i teraz zastanawiam się, czy istnieje sposób na znalezienie liczby irracjonalnej, która spełnia warunek. Na przykład, biorąc pod uwagę dane wejściowe 0.282842712474, chcę, aby wynik był równy sqrt (2)/5, a nie 431827/1526739, który generuje mój algorytm. Jedynym warunkiem jest to, że pierwsze cyfry wyniku (przekształcone z powrotem na zmiennoprzecinkowe) powinny być cyframi danych wejściowych, reszta nie ma znaczenia. Z góry dziękuję!

Answer 1

Wpadłem na rozwiązanie, które z danego zestawu możliwych mianowników i nominatorów znajduje najlepsze przybliżenie podanej liczby.

Przykładowo ten zestaw może zawierać wszystkie numery, które mogą być utworzone przez:
= radicand < = 100000
= root_index < = 20

Jeśli zestaw zawiera N elementów, niż ten roztwór znajdzie najlepsze przybliżenie w O (N log N).

W tym rozwiązaniu X oznacza mianownik i nominator Y.

1. sortować numery z zestawu
2. dla każdej liczby X z zestawu:
   wykorzystujące binarny znaleźć najmniejszy Y takie, że Y/X> = input_number
   porównać Y/X z aktualnie najlepszą zbliżenia input_number

nie mogłem się oprzeć i wdrożone go:

#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"); 
}