algorithm - 检测重复小数的算法？

Question

有没有一种算法可以计算出以下事情？

如果除法的结果是重复的小数（二进制）。
如果它重复，重复从哪个数字（表示为 2 的幂）开始？
哪些数字重复？

一些例子：

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

有没有办法做到这一点？效率是一个大问题。算法的描述比代码更受欢迎，但我会接受我能得到的答案。

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

score 10 · Accepted Answer

如果除数不是 2 的幂（通常，包含不与表示基数共享的素数）
重复周期长度将由被除数的最大素因子驱动（但与该因子表示的长度无关——见十进制的 1/7），但第一个周期长度可能与重复单元不同（例如11/28 = 1/4+1/7（十进制）。
实际周期将取决于分子。

score 8 · Accepted Answer

我可以给出一个提示——以十为底的重复小数都是分数，分母至少有一个除二和五以外的质因数。如果分母不包含质因数二或五，它们总是可以用全九的分母来表示。然后提名者是重复部分，九的个数是重复部分的长度。

3     _
- = 0.3
9

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

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

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

但我不记得如何推导出非重复部分及其长度。

这似乎很好地转化为基数二。只有分母为 2 次方的分数是不重复的。这可以通过断言仅设置分母中的单个位来轻松检查。

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

至于以十为底，我不知道如何处理包含但不是 2 的幂的分母 - 例如 12 = 3 * 2^2。

score 5 · Accepted Answer

首先，你的一个例子是错误的。的重复部分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。重复十进制表示的关键部分是通过除以2 或其任意倍数生成的。因此，您可以找到一种方法来表达分母（例如构建常量表），或者进行大数除法（相对慢）并找到循环。没有快速的方法可以做到这一点。(2ⁿ - 1)

score 3 · Accepted Answer

3

查看小数扩展，特别是关于分数的周期。

于 2009-08-22T09:37:30.613 回答

score 2 · Accepted Answer

您可以进行长除法，注意余数。余数的结构将为您提供任何有理小数的结构：

最后的余数为零：它是一个没有任何重复部分的小数
第一个和最后一个余数相等：小数在点之后重复
第一个和第一个余数之间的距离等于最后一个是不重复的数字，余数是重复的部分

一般来说，距离会给你每个部分的位数。

您可以在此处的方法中看到这个用C++编码的算法。decompose()

试一下 228142/62265，它有一个1776位数的句号！

score 1 · Accepted Answer

要查找重复模式，只需跟踪沿线使用的值：

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”（小数分隔符后的第一个）。

如果您希望模式以“1”开头，您可以旋转它直到它匹配该条件：

"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
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.

algorithm - 检测重复小数的算法？

6 回答 6

Related

Reference