algorithm - 10 進数から無理数への近似

Question

浮動小数点数から有理分数への近似 (例: 0.333 -> 1/3) のアルゴリズムを実装しましたが、条件を満たす無理数を見つける方法はあるのでしょうか。たとえば、入力 0.282842712474 が与えられた場合、アルゴリズムが生成する 431827/1526739 ではなく、結果を sqrt(2)/5 にする必要があります。唯一の条件は、(浮動小数点に変換された) 結果の最初の桁が入力の桁であることであり、残りは重要ではありません。前もって感謝します！

Answer 1

私は解決策を思いつきました。それは、可能な分母と分母の与えられたセットから、与えられた数の最良の近似を見つけるというものです。

たとえば、このセットには、次の方法で作成できるすべての数値を含めることができます。1 <= radicand <
= 100000
1 <= root_index <= 20

セットにN個の要素がある場合、このソリューションはO（N log N）で最良の近似を見つけます。

このソリューションでは、Xは分母とYの分母を表します。

1. セットから番号を並べ替える
2. セットからの各数値Xについて：
   バイナリを使用して、Y / X>=input_numberとなる最小のYを見つけます
   。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");
}