长除法中余数的模式匹配

Question

我有一个可行的算法，可以确定分数是否无限循环，并确定哪些数字是重复的：

std::vector<integer_type> rd, dg;
integer_type d ( m_numer ), r;

do {

    integer_type q, aux;

    rd.push_back ( r = ( aux = _remquo<T, GCD, CHKOP> () ( d, m_denom, q ) ) < zero_ ?
                       integer_type ( -aux ) : aux );
    dg.push_back ( q < zero_ ? integer_type ( -q ) : q );

    d = op_multiplies() ( base, r );

} while ( ! ( r == zero_ || std::find ( rd.rbegin() + 1, rd.rend(), r ) != rd.rend() ) );

注意：

• rd 包含余数数字
• dg 包含十进制结果数字
• _remquo 整除第一个和第二个操作数，并将余数存储在第三个参数中，忽略模板参数
• base 可以视为十进制值 10
• m_numer 是一个分数的分子
• m_denom 是一个分数的分母

问题：

我想要摆脱至少std::find ( rd.rbegin() + 1, rd.rend(), r ) != rd.rend() )，也就是说，我想要检测是否之前出现过一次余数，并且最好（为了同时摆脱rd向量），返回自右向左的最后一位重复数字到第一个重复数字的距离。

问题是，我想要分析具有巨大的重复数字序列的数字，例如1083448249/12172166，并且要在合理的时间内完成（不需要花费时间去反向搜索余数向量）。

有人有什么想法吗？

- Heiko Schäfer

---

直接计算重复数字不是比实际执行长除法来检测重复数字更容易吗？ - JSF

@JSF 如果您有其他算法，请随时向我展示。 我需要最终结果以及重复数字和（如果有）小数点后直接的非重复数字。 13/30 => 0.4(3) - Heiko Schäfer

@HeikoSchäfer 这个问题可以简化为 1/N 的情况。对于这种情况，请参阅此链接：http://mathforum.org/library/drmath/view/51549.html（可推广到任何基数）。 - freakish

@freakish 谢谢你提供的链接，我会仔细阅读的 :) - Heiko Schäfer

根据Wikipedia的说法，“if”可以通过质因数分解来解决。你也可以代数地找到循环节的长度，这样你就知道何时找到了它。当然，它是否能在合理的时间内解决是另一个问题。 - molbdnilo

Answer 1

直接计算小数的位数，无需使用 bignums（大整数）。使用 Floyd 的循环检测方法来确定周期。以下为 Python 代码（循环检测代码由 Wikipedia 提供）：

#!/usr/bin/env python3
def floyd(f, x0):
    tortoise = f(x0)
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
    return (lam, mu)


def repeating_decimal(n, d):
    q, r = divmod(n, d)
    decimal = [str(q), '.']
    period, first_repeat = floyd(lambda r: 10 * r % d, r)
    for i in range(first_repeat + period):
        q, r = divmod(10 * r, d)
        decimal.append(str(q))
    return '{}({})'.format(''.join(decimal[:2 + first_repeat]), ''.join(decimal[2 + first_repeat:]))


print(repeating_decimal(1, 75))
print(repeating_decimal(1083448249, 12172166))

- David Eisenstat

---

哇塞！好的，这是Python和另一个算法，但我想我会将它转换成C++并尝试一下 :) - Heiko Schäfer

@HeikoSchäfer 对我来说最适合随意尝试的语言。当您将lambda内联到循环检测器中时，有简化的机会。 - David Eisenstat

你让我今天过得很开心 :) 我已经将它转换为C ++并集成到我的代码中（尽管未经优化），而且所有测试用例都没有错误！谢谢 :-) - Heiko Schäfer