algorithm - Log(n) 中的四联数

Question

我偶然发现了一个问题，它要求我计算第 n 个 Tetranacci Number在 O(log n) 中。

我已经看到针对 Fibonacci Numbers 执行此操作的几种解决方案

我一直在寻找遵循类似的程序(矩阵乘法/快速加倍)来实现这一点，但我不确定如何准确地做到这一点(以类似的方式采用 4 x 4 矩阵和 1 x 4 并没有似乎工作)。使用动态编程/通用循环/任何其他基本思想，我无法实现亚线性运行时间。任何帮助表示赞赏!

Answer 1

矩阵乘法当然有效。以下是推导矩阵的方法。

我们想要的是找到构成等式的条目

[a b c d] [T(n-1)]   [T(n)  ]
[e f g h] [T(n-2)]   [T(n-1)]
[i j k l] [T(n-3)] = [T(n-2)]
[m n o p] [T(n-4)]   [T(n-3)]

对所有 n 都为真。展开。

a T(n-1) + b T(n-2) + c T(n-3) + d T(n-4) = T(n)
e T(n-1) + f T(n-2) + g T(n-3) + h T(n-4) = T(n-1)
i T(n-1) + j T(n-2) + k T(n-3) + l T(n-4) = T(n-2)
m T(n-1) + n T(n-2) + o T(n-3) + p T(n-4) = T(n-3)

这里明显的设置是a = b = c = d = 1(使用循环)和e = j = o = 1和f = g = h = i = k = l = m = n = p = 0(基础代数)。

初始向量为

[T(3)]   [1]
[T(2)]   [0]
[T(1)] = [0]
[T(0)]   [0]

根据定义。