algorithm - 小数到无理分数逼近

Question

我已经实现了一个浮点小数到有理分数近似的算法（例如：0.333 -> 1/3），现在我想知道，有没有办法找到一个满足条件的无理数。例如，给定输入 0.282842712474 我希望结果是 sqrt(2)/5 而不是我的算法产生的 431827/1526739。唯一的条件是结果的第一个数字（转换回浮点数）应该是输入的数字，其余的无关紧要。提前致谢！

Answer 1

我想出了解决方案，即从给定的可能分母和提名集合中找到给定数字的最佳近似值。

例如，这个集合可以包含所有可以通过以下方式创建的数字：
1 <= radicand <= 100000
1 <= root_index <= 20

如果 set 有 N 个元素，则此解决方案在 O(N log N) 中找到最佳近似值。

在这个解决方案中，X 代表分母，Y 代表。

1. 从集合中排序数字
2. 对于集合中的每个数字 X：
   使用二进制找到最小的 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");
}