1

10進数のxが与えられた場合、xが分母が9999以下の有理数の10^-12以内にあるかどうかをテストしたいと思います。明らかに、x、2x、3xなどを調べて、これらのいずれかが整数に十分に近いかどうかを確認することで、それを行うことができます。しかし、より効率的なアルゴリズムはありますか？

4

3 に答える 3

5

連分数アルゴリズムと呼ばれるアルゴリズムがあり、特定の定義された意味で「最良の」有理近似を提供します。分母が9999を超えたら停止してから、前の収束に戻って比較し、十分に近いかどうかを確認できます。もちろん、小数が十分に小さい有理数である場合、アルゴリズムは早期に終了します。

于 2010-10-14T00:59:54.693 に答える
2

だから、いくつかのこと：

'decimal x'によって、浮動小数点表現xを参照していると思います。つまり、これを実際には.1や1/3などを完全に表すことができない形式で実装する予定です。これを手動で行う場合や、小数を表す独自の方法がある場合は、これは行われません。 t適用します。

第二に、あなたはそれらの特定の分母と許容範囲に縛られていますか？2の累乗（たとえば、2 ^ -35の許容誤差で最大8192の分母）で問題がない場合は、IEEE-754スタイルの浮動小数点がすべて有理数であるという事実を簡単に利用できるためです。指数を使用して、仮数のどの桁が2 ^ -13に対応するかを判別し、仮数の次の22桁が0（または、そのポイントを超える22を含めるのに十分な精度でない場合は最大22）であることを確認します。もしそうなら、あなたはそれを持っています。

さて、ベース2を使用するようにアルゴリズムを変更したくない場合は、少なくともこれを使用してアルゴリズムを絞り込み、ある程度の除去を行うことができます。

于 2010-10-14T01:08:19.050 に答える
1

あなたはすでに答えを受け入れているようですが、とにかくチャイムを鳴らします。

強引な方法では、すべての分母をチェックする必要はありません。逆方向に作業すると、チェックした数だけでなく、そのすべての要素を削除できます。たとえば、9999をチェックしたら、3333、1111、909、303、101、99、33、11、9、3、または1をチェックする必要はありません。数値がそれらの1つの分数として表現できる場合は、9999の分数としても表現できます。5000未満のすべての数値は、少なくとも1つの数値5000から9999の因数であることが判明したため、カットしました。検索スペースが半分になります。

編集：この問題は、Pythonでソリューションをコーディングするのに十分興味深いものであることがわかりました。

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def simplify(fraction_tuple):
    divisor = gcd(fraction_tuple[0], fraction_tuple[1])
    return fraction_tuple[0] / divisor, fraction_tuple[1] / divisor

def closest_fraction(value, max_denominator=9999, tolerance=1e-12, enforce_tolerance=False):
    best_error, best_result = abs(value), (0,1)
    for denominator in range(max_denominator/2+1, max_denominator+1):
        numerator = round(value * denominator)
        error = abs(value - (numerator / denominator))
        if error < best_error:
            best_error = error
            best_result = int(numerator), denominator
            if error <= tolerance:
                break
    if enforce_tolerance and best_error > tolerance:
        return None
    return simplify(best_result)
于 2010-10-14T08:47:04.427 に答える