有一个很好的技巧来计算给定浮点数的理性逼近(基于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我们的分数正在终止.

如果你真的想知道这个分数的重复部分是什么(什么数字和什么时期),你需要做一些额外的技巧.这涉及到所有这些因素(除了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位数字才能知道.