Approssimazione decimale a frazione irrazionale

Question

Ho implementato un algoritmo per l'approssimazione decimale in virgola mobile e l'approssimazione della frazione razionale (esempio: 0,333 -> 1/3) e ora mi chiedo, c'è un modo per trovare un numero irrazionale che soddisfi la condizione. Ad esempio, dato l'input 0.282842712474 voglio che il risultato sia sqrt (2)/5 e non 431827/1526739 che il mio algoritmo produce. L'unica condizione è che le prime cifre del risultato (convertite di nuovo in virgola mobile) debbano essere le cifre dell'input, il resto non ha importanza. Grazie in anticipo!

Answer 1

Mi è venuta in mente una soluzione, che dal set dato di possibili denominatori e nominatori trova la migliore approssimazione di un dato numero.

Ad esempio, questo insieme può contenere tutti i numeri che possono essere creati da:
= radicand < = 100000
= root_index < = 20

Se insieme ha N elementi, di questa soluzione constata migliore approssimazione in O (N log N).

In questa soluzione X rappresenta denominatore e Y nominator.

1. numeri di ordinamento della serie
2. per ogni numero X della serie:
   utilizzando binario trovare più piccola Y tale che Y/X> = numero_ingresso
   confronta Y/X con attualmente migliore approssimazione numero_ingresso

non ho resistito e ho realizzato che:

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