日志中的Tetranacci编号(n) [英] Tetranacci Numbers in Log(n)

问题描述

我偶然发现了一个问题，该问题要求我计算第n个 Tetranacci编号在O(log n)中.

I have stumbled upon a problem, which requires me to calculate the nth Tetranacci Number in O(log n).

我已经看到几种针对斐波那契数字

我希望遵循类似的过程(矩阵乘法/快速加倍)来实现此目的，但是我不确定如何准确地做到这一点(以类似的方式获取4×4矩阵和1×4矩阵)似乎有效).使用动态编程/通用循环/任何其他基本概念，我无法实现亚线性运行时.任何帮助表示赞赏！

I was looking to follow a similar procedure (Matrix Multiplication/Fast Doubling) to achieve this, but I am not sure how to do it exactly (take a 4 by 4 matrix and 1 by 4 in a similar fashion doesn't seem to work). With dynamic programming/general loops/any other basic idea, I am not able to achieve sub-linear runtime. Any help appreciated!

推荐答案

来自 OEIS ，这是( 1,4)输入

From the OEIS, this is the (1,4) entry of the nth power of

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

要在O(log n)操作中计算该矩阵的n次幂，可以使用通过平方求幂.递归可能会稍微简单一些，但是您应该能够实现常规技术.

To compute the nth power of that matrix in O(log n) operations, you can use exponentiation by squaring. There might be a slightly simpler recurrence, but you should be able to implement the general technique.

这篇关于日志中的Tetranacci编号(n)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！