1
$\begingroup$

I am trying to compute the continuant of a list of numbers $a_0, a_1,...,a_n$, defined by the recursion relation: $K_{n+1} = a_{n+1} K_n + K_{n-1}$ and $K_0 = 1$ (see Wikipedia).

I am trying to use divide-and-conquer as suggested by Knuth, 1971, Page 271-272.

However, my implementation:

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);
    }
}

runs in $O(n^2)$ time instead of semi-linear time.

$\endgroup$
  • $\begingroup$ I am using the mpir library for arbitrary precision arithmetic $\endgroup$ – Syed Fahad May 3 at 7:53
  • $\begingroup$ It turns out you need to cache the already calculated convergents and combine them to achieve the quasi-linear runtime. $\endgroup$ – Syed Fahad May 13 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.