# Unable to achieve semi-linear running time in computation of continuant

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.

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