检测循环小数的算法？

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），我可以直接使用它。我之所以这样说是因为如果你解释起来可能更容易以十进制来解释 :)

- Imagist

---

你使用了哪些条件来得出这个结果？为什么重复的数字不是"01"，"01"，"10"和"0011"？ - Guffa

@Guffa 我的想法是先放置1，因为前导零不是有效数字，而尾随零是。如果数字是类似"111.010101..."的东西，那么重复的数字将是"01"，因为在这种情况下第一个0是有效的。 - Imagist

@Guffa（接上）不过这对我并不重要。如果您告诉我如何以返回“01”、“01”、“01”和“0011”的方式来完成此操作，我会很满意的 :) - Imagist

听起来像是 http://projecteuler.net/problem=26 ；-) - schoetbi

Answer 1

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

- Steve Gilham

---

+1 感谢您的评论。这为我提供了一些关于问题的见解。特别是周期长度和实际周期由不同因素驱动的想法非常重要。我知道这对于存储周期很重要，但我没有考虑到它对于计算周期可能也很重要。然而，我仍然不知道如何计算这些信息。 - Imagist

Answer 2

我可以给你一个提示——在十进制下，循环小数都是分母至少有一个除了2和5以外的质因子的分数。如果分母不含2或5作为质因子，它们总是可以表示为所有数字都为9的分母。那么分子就是循环部分，而9的个数就是循环部分的长度。

3     _
- = 0.3
9

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

如果分母中有质因数2或5，循环部分并不从第一个位置开始。

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。

- Daniel Brückner

---

根据这个逻辑，那么在二进制中，循环小数是分母具有2以外的质因子的分数（我知道这一点）。我不知道如果它们有一个质因子1，它会从其他位置开始（这是有帮助的信息！）。 - Imagist

Answer 3

首先，你的一个例子是错误的。 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)或其任何2的倍数来生成的。所以你可以找到表达你的分母的方式（如构建常数表），或者进行大数除法（相对较慢）并找到循环。没有快速的方法来做这件事。

- Todd Li

---

+1 针对您的技术输入。然而，Guffa 的方法似乎非常有效，并且似乎与数字长度成线性关系，这足够快，因为这可能最常用于较小的数字。虽然这使我能够支持任意精度的浮点运算，但真正的目的是保持基数 10 数字的精确性（即在大多数语言中，由于重复的小数，1.1 基数 10 变成 1.100000001 或类似的数字）。 - Imagist

实际上，根据您的目的，有更好的方法：您可以将有理数保留在分数形式中，而不是将它们展开，或者您可以直接在十进制中进行计算。处理重复小数并不像我想象的那么容易。 :) - Todd Li

Answer 4

你可以进行一次长除法，注意余数。余数的结构将给出任何有理小数的结构：

1. 最后一个余数为零：它是一个没有任何重复部分的小数
2. 第一个和最后一个余数相等：小数点右边就开始重复了
3. 第一个余数与最后一个余数之间的距离是不重复的数字，余数是重复的部分

通常来说，这些距离会给出每个部分的数字数量。

你可以在这里的方法decompose()中用C++编写此算法。 尝试228142/62265，它有一个长度为1776的周期！

- Heiko Schäfer

Answer 5

请查看十进制展开，特别是关于分数周期的部分。

- Nick Dandoulakis

---

+1 谢谢你的帖子。这帮助我理解了问题。 - Imagist

Answer 6

要找到重复的模式，只需沿着该行跟踪您使用的值：

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.

- Guffa

---

我不确定这是否解决了他的问题，因为有些分数在一定数量的数字后会重复，例如5/6 = .8333333。因此，在您的模型下，它将使用8来找到重复。 - user20844

@letseatunch：5/6 = 101/110 = 0.11010101010101010... 如果你运行FindPattern(5,6)，它将从第-2位数字开始找到重复的模式，长度为2。 - Guffa

我花了一点时间来理解你的代码，因为我不太熟悉C#，但我认为这正是我在寻找的。我正在用C++编写这个程序，数字存储方式并不完全相同，但移植起来应该很容易。非常感谢你的帮助！ - Imagist

Answer 7

正如其他人所指出的那样，答案涉及长除法。

这里有一个简单的Python函数可以完成这个任务：

def longdiv(numerator,denominator):
    digits = []
    remainders = [0]
    n = numerator
    while n not in remainders:              #   until repeated remainder or no remainder
        remainders.append(n)                #   add remainder to collection
        digits.append(n//denominator)       #   add integer division to result
        n = n%denominator * 10              #   remainder*10 for next iteration

    #   Result
    result = list(map(str,digits))          #   convert digits to strings
    result = ''.join(result)                #   combine list to string

    if not n:
        result = result[:1]+'.'+result[1:]  #   Insert . into string
    else:
        recurring = remainders.index(n)-1   #   first recurring digit
        #   Insert '.' and then surround recurring part in brackets:
        result = result[:1]+'.'+result[1:recurring]+'['+result[recurring:]+']'

    return result;

print(longdiv(31,8))    #   3.875
print(longdiv(2,13))    #   0.[153846]
print(longdiv(13,14))   #   0.9[285714]

这段代码有详细的注释，因此在其他编程语言中编写应该不会太难，比如JavaScript。

关于循环小数，最重要的部分包括：

• 保留余数的集合；第一个余数为0是为了方便下一步操作
• 进行除法运算，记录整数商和余数
• 如果新余数为0，则得到一个有限小数
• 如果新余数已经在集合中，则得到一个循环小数
• 重复、自由发挥和淡出等

函数的其余部分用于格式化结果。

- Manngo