c++ - 长除法余数的模式匹配

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 vector )从右到左的最后一个数字与 中的第一个重复数字之间的距离rd.

问题是，我想分析具有 HUGE 重复数字序列的数字，例如 1083448249/12172166在合理的时间内(不花时间反向搜索余数 vector 的时间)。

有人有什么想法吗？

Answer 1

直接计算小数展开式的位数，不使用大数。使用 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))