c# - 如何检测 float 是否在 C# 中具有重复的小数扩展？

Question

我只需要知道如何检测 float 中重复的小数扩展。

例子:

0.123456789123456789

数字的重复部分将是 123456789。

我想在 C# 中自动执行此操作，是否有任何智能解决方案？

Answer 1

有一个很好的技巧可以计算给定 float 的有理近似值(基于 GCD 的欧几里德算法的某些属性)。我们可以使用它来确定“最佳”近似值是否为 A/(2^a 5^b) 形式，如果是，则浮点终止(以 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 的整数部分粘贴到该表的第一行，称它们为 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 的形式，因此我们的十进制展开是重复的。

请注意，虽然这似乎需要很多步骤，但如果我们使用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 没有公共(public)因子，因此您无需担心抵消因子或类似问题。

为了比较，让我们看一下 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 我们的分数正在终止。

如果您真的想找出分数的重复部分是什么(什么数字和什么周期)，您需要做一些额外的技巧。这涉及分解分母并找到具有所有这些因数(2 和 5 除外)的最小数字 (10^k-1)，然后 k 将是您的期间。所以对于我们的顶级案例，我们发现 A = 9999 = 10^4-1(因此 10^4-1 包含 A 的所有因子 - 我们在这里很幸运......)所以重复部分的周期是 4 . 您可以找到有关最后一部分 here 的更多详细信息。

这个算法的最后一个重要方面是它不需要所有数字都将小数扩展标记为重复。考虑 x = 0.34482，这有表格:

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

我们在第二个条目处得到一个非常准确的近似值并停在那里，得出的结论是我们的分数可能是 10/29(因为它在 1e-5 内使用)并且从上面链接中的表格我们可以看出它的周期将是 28 位数字。这永远无法通过对数字的短版本进行字符串搜索来确定，这需要知道至少 57 位数字。