Decimal value for approximating the irrational fraction

Question

I applied the floating point decimal algorithm to approximate the rational fraction (example: 0.333 → 1/3), and now I am wondering if there is a way to find an irrational number that satisfies the condition. For example, given the input 0.282842712474, I want the result to be sqrt (2) / 5, and not 431827/1526739, which produces my algorithm. The only condition is that the first digits of the result (converted back to a floating point) must be input digits, the rest does not matter. Thanks in advance!

Answer 1

I came up with a solution that from a given set of possible denominators and nominators finds the best approximation of a given number.

For example, this set can contain all the numbers that can be created: 1 <= radicand <= 100000
1 <= root_index <= 20

If the collection has N elements, then this solution finds the best approximation in O (N log N).

In this decision, X represents the denominator and Y nominee.

• sort numbers from a set
• for each number X from the set:
  using binary search of smallest Y such that Y / X> = input_number
  compare y / x with best approximation currently input_number

I could not resist, and I implemented it:

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