Dezimal zu Irrational Fraktion Approximation

Question

Ich habe einen Algorithmus für Fließkomma-Dezimalstellen auf rationale Bruchteil-Approximation implementiert (Beispiel: 0,333 -> 1/3) und nun frage ich mich, gibt es eine Möglichkeit, eine irrationale Zahl zu finden, die die Bedingung erfüllt. Zum Beispiel möchte ich bei der Eingabe 0.282842712474, dass das Ergebnis sqrt (2)/5 und nicht 431827/1526739 ist, was mein Algorithmus erzeugt. Die einzige Bedingung ist, dass die ersten Ziffern des Ergebnisses (in Fließkommazahl zurückgerechnet) die Ziffern der Eingabe sein sollten, der Rest spielt keine Rolle. Danke im Voraus!

Answer 1

Ich kam mit der Lösung, dass aus einer gegebenen Menge von möglichen Nenner und Nenner besten Approximation der gegebenen Zahl findet.

Zum Beispiel dieser Satz alle Zahlen enthalten kann, die erstellt werden können:
= Radikanden < = 100000
= root_index < = 20

Wenn gesetzt N Elemente aufweist, als diese Lösung findet beste Näherung in O (N log N).

In dieser Lösung steht X für Nenner und Y für Nenner.

1. Sortiernummern von Satz
2. für jede Nummer X aus der Serie:
   mit binären finden kleinsten Y, so dass Y/X> = input_number
   vergleichen Y/X mit derzeit beste Annäherung an input_number

ich konnte nicht widerstehen, und ich setzte es:

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