我正在尝试计算由递归关系定义和（参见维基百科）。$a_0, a_1,...,a_n$$K_{n+1} = a_{n+1} K_n + K_{n-1}$$K_0 = 1$

我正在尝试按照Knuth, 1971, Page 271-272的建议使用分而治之。

但是，我的实现：

mpz_class continuant(size_t s, size_t t, ConvergentList& convergents) {
    if (s == t) return convergents[s];
    if (t - s <= 2) {  // 2 can be adjusted
        mpz_class k_n = convergents[s++], k_n1 = 1, temp;
        while (s != t) {
            temp = k_n1;
            k_n1 = k_n;
            k_n = convergents[s++] * k_n + temp;
        }
        return k_n * convergents[s] + k_n1;
    }
    else {
        auto mid = s + (t - s) / 2;
        return continuant(s, mid, convergents) * continuant(mid + 1, t, convergents)
        + continuant(s, mid - 1, convergents) * continuant(mid + 2, t, convergents);
    }
}

以时间而不是半线性时间运行。$O(n^2)$