Abi*_*Abi 9 c# math floating-point design-patterns period
我只需要知道如何在浮点数中检测重复的十进制扩展.
例:
0.123456789123456789
该数字的重复部分为123456789.
我想用C#自动化这个,有没有智能解决方案？
计算给定float的有理逼近有一个很好的技巧(基于Euclid 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的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的形式写入,因此我们的十进制扩展是重复的.
请注意,虽然这似乎需要很多步骤,但如果我们使用x = 1/x - round(1/x)(并且跟踪轮回(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你可以在这里找到关于这个最后部分的更多细节.
不是这种算法的最后一个重要方面是它不要求所有数字都将十进制扩展标记为重复.考虑x = 0.34482,这有表:
3 -10 -156
1 0 1 -10 .
0 1 3 -29 .
我们在第二个条目得到一个非常精确的近似值并在那里停止,得出结论我们的分数大概是10/29(因为它在1e-5内使用),并且从上面链接的表中我们可以看出它的周期将是28数字.使用短号版本的字符串搜索永远无法确定这一点,这需要至少57位数字才能知道.
您无法像示例中那样检测以 10 为基数表示的句点，浮点数的精度为 7 位数字。
http://msdn.microsoft.com/en-us/library/aa691146%28v=vs.71%29.aspx