9

float で繰り返される 10 進展開を検出する方法を知る必要があるだけです。

例:

0.123456789123456789

番号の繰り返し部分は 123456789 になります。

これを C# で自動化したいのですが、スマートな解決策はありますか?

4

6 に答える 6

8

与えられた float の有理近似を計算するための優れたトリックがあります (GCD に対する Euclid アルゴリズムのいくつかのプロパティに基づいています)。これを使用して、「最良の」近似が の形式であるかどうかを判断できますA/(2^a 5^b)。そうである場合、float は (基数 10 で) 終了し、そうでない場合は、繰り返しコンポーネントを持つことになります。トリッキーなビットは、どの近似が正しいものであるかを判断することです (浮動小数点の精度の問題のため)。

近似有理式を取得する方法は次のとおりです。

最初x = 1/x - floor(1/x)の反復追跡int(x)

x = 0.12341234
1/x = 8.102917
x <= 1/x - 8 = 0.102917
1/x = 9.7165
x <= 1/x - 9 = 0.71265277
1/x = 1.3956
x < 1/x - 1 = 0.3956
...

次に、x の int 部分をこのテーブルの一番上の行に貼り付け、それらを k_i と呼びます。の値A_i = A_{i-2} + k_i * A_{i-1}と同じですB_i

           ||  8      |  9  | 1   | 2   | 1   |  1  |    8 |    1 |    1
A =    1 0 ||  1      |  9  | 10  | 29  | 39  |  68 |  583 |  651 | 1234
B =    0 1 ||  8      | 73  | 81  | 235 | 316 | 551 | 4724 | 5275 | 9999

有理近似はA_n/B_nです。

1/8       = 0.12500000000000000     | e = 1.5e-3
9/73      = 0.12328767123287671     | e = 1.2e-4
10/81     = 0.12345679012345678     | e = 4.4e-5
29/235    = 0.12340425531914893     | e = 8.1e-6
39/316    = 0.12341772151898735     | e = 5.4e-6
68/551    = 0.12341197822141561     | e = 3.6e-7
583/4724  = 0.12341236240474174     | e = 2.2e-8
651/5275  = 0.12341232227488151     | e = 1.8e-8
1234/9999 = 0.12341234123412341     | e = 1.2e-9

したがって、1234/9999 の段階で誤差が十分に小さいと判断した場合、9999 は 2^a 5^b の形式で記述できないため、10 進展開が繰り返されることに注意してください。

これには多くの手順が必要なように見えますが、 x = 1/x - round(1/x)(代わりに round round(1/x) を追跡) を使用すると収束が速くなることに注意してください。その場合、テーブルは次のようになります

     8  10    -4     2      9     -2
1 0  1  10   -39   -68   -651   1234
0 1  8  81  -316  -551  -5275   9999

これにより、以前の結果のサブセットが少ない手順で得られます。

分数 A_i/B_i は常に A_i と B_i に共通の因数がないため、因数の相殺などについて心配する必要がないことに注意するのは興味深いことです。

比較のために、x = 0.123 の展開を見てみましょう。得られるテーブルは次のとおりです。

      8   8   -3    -5  
 1 0  1   8  -23   123
 0 1  8  65 -187  1000

次に、近似のシーケンスは次のとおりです。

 1/8      = 0.125       e = 2.0e-3
 8/65     = 0.12307..   e = 7.6e-5
 23/187   = 0.12299..   e = 5.3e-6
 123/1000 = 0.123       e = 0

そして、123/1000 がまさに必要な分数であることがわかり、1000 = 10^3 = 2^3 5^3 なので分数は終了します。

分数の繰り返し部分が何であるか (どの桁とどのピリオドか) を実際に調べたい場合は、いくつかの追加のトリックを行う必要があります。これには、分母を因数分解し、(10^k-1)それらすべての因数 (2 と 5 以外) で最小の数を見つけることが含まれ、k がピリオドになります。したがって、最上位のケースでは、A = 9999 = 10^4-1 (したがって、10^4-1 には A のすべての要素が含まれます。ここでは幸運でした...) が見つかりました。したがって、繰り返し部分の周期は 4 です。 . この最終部分の詳細については、こちらを参照してください

このアルゴリズムの最後の重要な側面は、10 進展開を繰り返しとしてマークするためにすべての桁を必要としないことです。x = 0.34482 を考えてみましょう。これには次の表があります。

     3 -10 -156
1 0  1 -10   . 
0 1  3 -29   .

2 番目のエントリで非常に正確な概算を取得し、そこで停止します。分数はおそらく 10/29 (1e-5 内で使用されるため) であると結論付け、上記のリンクの表から、その周期が 28 になることがわかります。数字。これは、番号の短いバージョンでの文字列検索を使用して決定することはできませんでした。これには、少なくとも 57 桁の番号を知る必要があります。

于 2012-08-24T01:03:48.000 に答える
2

あなたの例のように基数10での表現のようにピリオドを検出することはできません.floatの精度は7桁です.

http://msdn.microsoft.com/en-us/library/aa691146%28v=vs.71%29.aspx

于 2012-08-23T19:14:17.387 に答える
1

できません。

浮動小数点の精度は有限です。タイプのすべての値はfloat、2.0の整数乗の整数倍(X * 2 Y)です。ここで、XとYは(おそらく負の)整数です)。10は2の倍数であるため、タイプのすべての値は、有限の10進数で正確floatに表すことができます。

たとえば1.0f/3.0f、循環小数(または2進数)として表されることを期待するかもしれませんが、実際には、循環小数ではないfloat数学値の近似値しか保持できません(循環小数に続く繰り返しを数えない限り)ゼロ以外の数字)。保存された値は正確に;である可能性があります。小数点以下の最初の7桁程度だけが重要です。00.3333333432674407958984375

于 2012-08-26T00:48:33.337 に答える
1

次のように、数値の小数 (ポストピリオド) 部分を分離できます。

value - Math.Floor(value)

double 値「1.25」でこれを行うと、値「0.25」になります。したがって、「ピリオドの右側」の部分が分離されます。もちろん、あなたの質問が必要とするように整数ではなく、0 から 1 の間の double として持つことになります。

あなたの質問は、「フロートのピリオドを検出する」必要があると述べています。小数部分が存在するかどうかを判断するだけでよい場合は、次のコードがほぼ機能します。

value != Math.Floor(value)
于 2012-08-23T23:41:44.617 に答える
1

個人的には、文字列に変換し、ピリオドの後にすべての部分文字列を引っ掛けてから、必要なデータ型に変換します。たとえば (C# を書いてから何年も経っているので、構文の問題は許してください):

float checkNumber = 8.1234567;
String number = new String( checkNumber ); // If memory serves, this is completely valid
int position = number.indexOf( "." ); // This could be number.search("."), I don't recall the exact method name off the top of my head
if( position >= 0 ){ // Assuming search or index of gives a 0 based index and returns -1 if the substring is not found
    number = number.substring( position ); // Assuming this is the correct method name to retrieve a substring.
    int decimal = new Int( number ); // Again, if memory serves this is completely valid
}
于 2012-08-24T00:08:06.450 に答える
0

I don't think that there's solution in general (at least, with float/double):

  • period can bee too long for float (or even double);
  • float/double are approximate values.

E.g., here's a result of division (double)1/(double)97:

0.010309278350515464

Indeed, it is a repeating decimal with 96 repeating digits in period. How to detect this, if you only have 18 digits after decimal point?

Even in decimal there's not enough digits:

0.0103092783505154639175257732
于 2012-08-23T19:26:18.387 に答える