Log(n)中的Tetranacci数

Question

我偶然发现了一个问题,这需要我计算O(log n)中的第n个Tetranacci数.

我已经看到了为Fibonacci数字做这个的几个解决方案

我希望遵循类似的程序(矩阵乘法/快速加倍)来实现这一目标,但我不确定如何完全做到这一点(以类似的方式采用4乘4矩阵和1乘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]

根据定义.

Answer 2

从OEIS来看，这是 n 次方的 (1,4) 项

1 1 0 0
1 0 1 0
1 0 0 1
1 0 0 0

要在 O(log n) 运算中计算该矩阵的 n 次方，您可以通过平方来使用幂运算。可能会有稍微简单的重现，但您应该能够实现通用技术。