2

重複の可能性:
浮動小数点数を、バイトの分子と分母で表される最も近い分数に変換するにはどうすればよいですか?

Javaで任意のfloatまたはdoubleを取り、それを有理数に変換したいと思います-つまり。a と b は倍長整数である a/b 形式の数。どうすれば合理的に効率的な方法でこれを行うことができますか?

(ところで、分数を単純化するためのコードは既にあるので、a/b が最も単純な形式であるかどうかは問題ではありません)。

4

5 に答える 5

5

最初に、IEEE-754 ルールによってdouble (または float ですが、以下では double のみを参照) がどのように構築されるかを確認します。

次に、 double を でビットに変換しますDouble.doubleToLongBits。この方法で端数を数え1 + bit_0 * 2^(-1) + bit_1 * 2^(-2) ...ます。結果に指数（2^(exponent)正確には）と符号を掛けます。

コードは次のとおりです。

double number =  -0.15625;
// Code below doesn't work for 0 and NaN - just check before

long bits = Double.doubleToLongBits(number);

long sign = bits >>> 63;
long exponent = ((bits >>> 52) ^ (sign << 11)) - 1023;
long fraction = bits << 12; // bits are "reversed" but that's not a problem

long a = 1L;
long b = 1L;

for (int i = 63; i >= 12; i--) {
    a = a * 2 + ((fraction >>> i) & 1);
    b *= 2;
}

if (exponent > 0)
    a *= 1 << exponent;
else
    b *= 1 << -exponent;

if (sign == 1)
    a *= -1;

// Here you have to simplify the fraction

System.out.println(a + "/" + b);

ただし、注意してください。指数が大きいと、変数に収まらない数値に遭遇する可能性があります。実際、分数に沿って指数を格納し、指数が十分に小さい場合にのみ乗算することを検討できます。そうではなく、分数をユーザーに表示する必要がある場合は、科学表記法を使用できます (これには2^n = x * 10^m、m が 10 進指数で、x が分数に掛けなければならない数値である方程式を解く必要があります。しかし、それは別の質問の問題です。 ...)。

于 2012-11-04T20:56:48.740 に答える
2

しましょうlong bits = Double.doubleToLongBits(double)。の Javadoc からDouble.longBitsToDouble:

...s、e、および m を、引数から計算できる 3 つの値にします。

int s = ((bits >> 63) == 0) ? 1 : -1;
int e = (int)((bits >> 52) & 0x7ffL);
long m = (e == 0) ?
             (bits & 0xfffffffffffffL) << 1 :
             (bits & 0xfffffffffffffL) | 0x10000000000000L;

この場合、浮動小数点の結果は、数式 s·m·2 e-1075の値と等しくなります。

その結果は間違いなく有理数です。

于 2012-11-04T23:45:47.280 に答える
1

ルーブリック連分数の下に含まれるさまざまな概念は、与えられた最大分母に対して可能な限り最良の有理近似を生成します。具体的には、収束シーケンスの計算について質問しています。ある時点で、必要な基準に従って分母が十分に大きくなった場合 (または有限の整数実装長によって強制された場合)、収束項の計算を終了し、最後の項を使用します。アルゴリズムは、リンクされたウィキペディアのページでかなり詳細に説明されています。

あなたが提起した 1 つの懸念に対処するために、収束シーケンスで生成された分数は常に縮小された形式になります。また、それらは、特定の分母に対して考えられる最良の近似値であることが証明されています。正確には、m/n の形式の収束項は、分母 < n の別の分数よりもターゲット数に近くなります。つまり、収束アルゴリズムは、試行錯誤よりも優れた近似値を生成します。

于 2012-11-05T00:27:42.607 に答える
1

任意の FP 値に対応する有理数は (仮数/2^-指数) であり、仮数と指数はIEEE 754 (Wiki 参照) で定義されています。次に、LCD（またはGCFだと思います）で除算を適用して、正規の有理数を取得できます。

于 2012-11-04T21:35:21.670 に答える
0

ご存知のように、浮動小数点数は0.1 のような単純な数値でさえ正確に格納できません。単純な方法で浮動小数点数を変換すると、分子と分母が巨大になる可能性があります。

ただし、役立つアルゴリズムがあります。Dragon4 および Grisu3アルゴリズムは、浮動小数点数に対して最も読みやすい出力を作成するように設計されています。それらは、特定の浮動小数点ビット シーケンスが複数の小数で表現できることを利用して、これらの中で最も短いものを選択します。

最初の実装では、Dragon4 および/または Grisu3 を使用して、浮動小数点から最短の小数を作成します。たとえば、ビットを含む浮動小数点数は、1.29999999ではなくcd cc cc cc cc cc f4 3f小数部1.3になります。次に、小数を a/b の形式で表し、簡略化します。与えられた例では、これは13/10であり、これ以上単純化する必要はありません。

小数への変換は不利になる場合がありますので注意してください。たとえば、有理数 1/3 は、10 進数と浮動小数点数の両方で正確に表すことはできません。したがって、最善の解決策は、Dragon4 などのアルゴリズムを変更して、10 だけでなく任意の分数分母を使用することです。

于 2012-11-04T21:26:18.190 に答える