我怎么能检测一个浮动在C＃中的循环小数扩张？ [英] How can I detect if a float has a repeating decimal expansion in C#?

问题描述

我只需要知道如何检测重复的花车十进制扩展

I simply need to know how I can detect repeating decimal expansion in floats.

例如：

0.123456789123456789

0.123456789123456789

数量的重复部分是123456789。

The repeating portion of the number would be 123456789.

我想在C＃中你完成这项，是有没有什么聪明的解决方案？

I want to automatize this in C#, is there any smart solution?

推荐答案

有对计算有理逼近给定的浮动（基于欧几里得算法的一些属性不错的技巧对于GCDS）。我们可以用它来确定最佳近似是否是形式 A /（2 ^ 5 ^ B），如果是则浮动终止（在基数为10），如果不是会有一些重复组件。棘手位将决定其近似值是正确的（由于浮点precission问题）。

There's a nice trick for calculating rational approximations to a given float (based on some properties of Euclid's algorithm for GCDs). We can use this to determine whether or not the "best" approximation is of the form A/(2^a 5^b), if it is then the float terminates (in base 10), if not it will have some repeating component. The tricky bit will be determining which of the approximations is the right one (due to floating point precission issues).

因此​​，继承人你如何得到近似有理式。

So heres how you get approximate rational expressions.

第一迭代 X = 1 / X - 地板（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

因此​​，如果我们决定我们的错误是在九千九百九十九分之一千二百三十四阶段足够低我们注意到，9999不能被写入的形式2 ^ 5 ^ b，并且因此我们的小数扩张重复

So if we decide our error is low enough at the 1234/9999 stage, we note that 9999 can not be written in the form 2^a 5^b, and thus our decimal expansion is repeating.

请注意，虽然这似乎要求很多步骤，如果我们使用
，我们可以得到更快的收敛 X = 1 / X - 圆（1 / X）（并跟踪道道（1 / X）来代替）。在这种情况下，表变为

Note that while this seems to require a lot of steps we can get faster convergence if we use x = 1/x - round(1/x) (and keep track of round round(1/x) instead). In that case the table becomes

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

这给你以前的结果，以更少的步骤的一个子集

This gives you a subset of the previous results, in fewer steps.

有趣的是，要注意，分数A_I / B_i总是使得A_I和B_i没有共同的因素，所以你不活动需要担心抵消因素或类似的东西。

It is interesting to note that the fraction A_i/B_i is always such that A_i and B_i have no common factors so you dont event need to worry about canceling out factors or anything like that.

有关比较让我们看看扩张X = 0.123。我们得到的表是：

For comparison lets look at the expansion for x = 0.123. The table we get is:

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

那么，我们的近似值的序列

Then our sequence of approximations is

 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

和我们看到1000分之123正是我们想要的分数，因为1000 = 10 ^ 3 = 2 ^ 3 ^ 5 3我们的部分被终止。

And we see that 123/1000 is exactly the fraction we want and since 1000 = 10^3 = 2^3 5^3 our fraction is terminating.

如果你真的想找出分数的重复的部分是什么（什么数字，什么时间），你需要做一些额外的技巧。这包括保理分母，并找到最低的数字（10 ^ K-1）与所有这些因素（2以外和5），则k将是你的时期。因此，对于我们的顶级情况下，我们发现A = 9999 = 10 ^ 4-1（因此10 ^ 4-1包含了所有的因素 - 我们是一种幸运在这里...），所以重复部分的时间段为4你可以找到这里最后部分更多细节。

If you actually want to find out what the repeating part of the fraction is (what digits and what period) you need to do some additional tricks. This involves factoring the denominator and finding the lowest number (10^k-1) with all those factors (other than 2 and 5), then k will be your period. So for our top case we found A = 9999 = 10^4-1 (and thus 10^4-1 contains all the factors of A - we were kind of lucky here...) so the period of the repeating part is 4. You can find more details about this final part here.

不是这个算法的最后一个重要的方面是，它不要求所有的数字来标记的十进制扩展的重复。考虑X = 0.34482，这有表：

A final and important aspect of not of this algorithm is that it does not require all the digits to mark a decimal expansion as repeating. Consider x = 0.34482, this has the table:

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

我们拿到的第二个条目非常精确的近似和停在那里，得出的结论是我们的分数大概是10 / 29（作为获得1E-5中使用），并从链接表上面我们可以看出，其期限为28位。这可能从未使用上的数字，这将要求将已知数量的至少57个数字的短版本字符串的搜索来确定。

We get a very accurate approximation at the second entry and stop there, concluding that our fraction is probably 10/29 (as that gets use within 1e-5) and from the tables in the link above we can discern that its period will be 28 digits. This could never be determined using string searches on the short version of the number, which would require at least 57 digits of the number to be known.

这篇关于我怎么能检测一个浮动在C＃中的循环小数扩张？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！