检测重复小数的算法？

Question

有没有一个算法来搞清楚下列事情？

1. 如果一个除法的结果是一个重复的十进制数（二进制）。
2. 如果重复，重复开始的位数是多少（表示为2的幂）？
3. 什么数字重复？

一些例子：

1/2 = 1/10 = 0.1 // 1 = false, 2 = N/A, 3 = N/A, 4 = N/A 
1/3 = 1/11 = 0.010101... // 1 = true, 2 = -2, 3 = 10 
2/3 = 10/11 = 0.101010... // 1 = true, 2 = -1, 3 = 10 
4/3 = 100/11 = 1.010101... // 1 = true, 2 = 0, 3 = 10 
1/5 = 1/101 = 0.001100110011... // 1 = true, 2 = -3, 3 = 1100 

有没有办法做到这一点？效率是一个大问题。该算法的描述将优于代码，但我会采取我能得到的答案。

还值得注意的是，基地并不是什么大不了的;我可以将算法转换为二进制（或者如果它在，比如基于256来使用char s，我可以简单地使用它）。我这样说是因为如果你解释它可能会更容易解释在基地10 :)。

Answer 1

要找到重复的图案，只是跟踪你沿线使用值：

1/5 = 1/101: 

1 < 101 => 0 
(decimal separator here) 
10 < 101 => 0 
100 < 101 => 0 
1000 >= 101 => 1 

    1000 - 101 = 11 

110 >= 101 => 1 

    110 - 101 = 1 

10 -> match 

当你到达相同的值，你必须在第二位，该进程将刚刚从重复点一遍又一遍地产生相同的位模式。您从第二位开始重复模式“0011”（小数点后第一位）。

"0011" from the second bit 
"0110" from the third bit 
"1100" from the fourth bit 

编辑：
实例C＃：

void FindPattern(int n1, int n2) { 
    int digit = -1; 
    while (n1 >= n2) { 
     n2 <<= 1; 
     digit++; 
    } 
    Dictionary<int, int> states = new Dictionary<int, int>(); 
    bool found = false; 
    while (n1 > 0 || digit >= 0) { 
     if (digit == -1) Console.Write('.'); 
     n1 <<= 1; 
     if (states.ContainsKey(n1)) { 
     Console.WriteLine(digit >= 0 ? new String('0', digit + 1) : String.Empty); 
     Console.WriteLine("Repeat from digit {0} length {1}.", states[n1], states[n1] - digit); 
     found = true; 
     break; 
     } 
     states.Add(n1, digit); 
     if (n1 < n2) { 
     Console.Write('0'); 
     } else { 
     Console.Write('1'); 
     n1 -= n2; 
     } 
     digit--; 
    } 
    if (!found) { 
     Console.WriteLine(); 
     Console.WriteLine("No repeat."); 
    } 
} 

如果你想在模式开始一个 “1”，你可以，直到它认为条件匹配其旋转与您的示例一起输出：

.1 
No repeat. 
.01 
Repeat from digit -1 length 2. 
.10 
Repeat from digit -1 length 2. 
1.0 
Repeat from digit 0 length 2. 
.0011 
Repeat from digit -1 length 4. 

Answer 2

1. 如果除数不是2的幂（在一般情况下，含有不与表示的基共享素因子）
2. 重复周期长度将被除数的最大素数因子被驱动（但不与该因子的表示长度相连 - 见十进制1/7），但第一个循环长度可能与重复单位不同（例如11/28 = 1/4 + 1/7十进制）。
3. 实际周期取决于分子。

Answer 3

退房decimal expansion，特别是关于一小部分的时期。

Answer 4

我可以给出一个提示 - 重复以10为底的小数都是分母，分母至少有一个除2和5以外的素因子。如果分母不包含两个或五个主要因素，则总是可以用所有九个分母来表示。然后提名者是重复的部分，9的数目是重复部分的长度。

3  _ 
- = 0.3 
9 

1 142857  ______ 
- = ------ = 0.142857 
7 999999 

如果分母中有两个或五个素数因子，则重复部分不在第一个位置。

17 17  ______ 
-- = ----- = 0.4857142 
35 5 * 7 

但我不记得如何派生非重复部分及其长度。

这似乎很好地转化为基础二。只有两个分母的幂的分数是不重复的。这可以通过声明分母中只有一位被设置来轻松检查。

1/2 = 1/10 = 0.1 
1/4 = 1/100 = 0.01 
3/4 = 11/100 = 0.11 
5/8 = 101/1000 = 0.101 

所有分数与奇分母应该重复和可通过表达与分母的分数的形式2^n-1来获得的图案和其长度。

             __ 
1/3   = 1/(2^2-1) =  1/11  = 0.01 
                __ 
2/3   = 2/(2^2-1) =  10/11  = 0.10 
         __ 
4/3 => 1 + 1/3 => 1.01 
         __ 
10/3 => 3 + 1/3 => 11.01 
                ____ 
1/5 = 3/15 = 3/(2^4-1) =  11/1111  = 0.0011 
                ________ 
11/17 = 165/255 = 11/(2^8-1) = 10100101/11111111 = 0.10100101 

至于碱10，我不能告诉如何处理包含分母但不是二的幂 - 例如12 = 3 * 2^2。

Answer 5

首先，你的一个例子是错误的。 1/5的重复部分是0011而不是1100，并且它从小数部分的最开始开始。

一个循环小数是这样的：在

a/b = c + d(2-n + 2-n-k + 2-n-2k + ...)
    = c + 2-n * d/(1 - 2-k)

n和d是你想要的。

例如，

1/10(dec) = 1/1010(bin) = 0.0001100110011... // 1 = true, 2 = -1, 3 = 0011

可以由式与

a = 1, b = 10(dec), c = 0, d = 0.0011(bin), n = 1, k = 4;
(1 - 2-k) = 0.1111

因此，1/10 = 0.1 * 0.0011/0.1111来表示。重复的十进制表示的关键部分是通过除以(2n - 1)或它的任意倍数来生成的。因此，您可以找到表达分母的方式（比如构建常量表），或者进行大数分割（这是相对较慢）并找到循环。没有快速的方法来做到这一点。

Answer 6

You ca n做一个long division，注意其余部分。余数的结构会给你任何理性小数的结构：

1. 最后的余数是零：这是一个没有任何重复的部分
2. 第一个和最后一个剩余相等十进制：在小数点后右重复
3. 所述第一和第一余数等于最后之间的距离是所述非重复的数字，其余的是重复部分

一般的距离无线会给你每个部分的数字量。

你可以看到这个算法的方法decompose()here在C++编码。

Try228142/62265，它有一个周期的数字！