Log(n) 中的四联数

Question

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

执行此操作的几种解决方案

我一直在寻找遵循类似的程序（矩阵 Multiplication/Fast 加倍）来实现这一点，但我不确定如何准确地做到这一点（采用 4 x 4 矩阵和类似的 1 x 4时尚似乎不起作用）。使用 dynamic programming/general loops/any 其他基本思想，我无法实现亚线性运行时。任何帮助表示赞赏！

Answer 1

从OEIS开始，这是

的n次方的(1,4)项

要在 O(log n) 次运算中计算该矩阵的 n 次方，您可以使用 exponentiation by squaring。可能有一个稍微简单的递归，但你应该能够实现通用技术。

Answer 2

矩阵乘法课程作品。下面是推导矩阵的方法。

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

[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 3

我已经从其他答案中描述的相应矩阵推导出 Tetranacci 加倍公式。公式是：

T(2n)   = T(n+1)*(2*T(n+2) - T(n+1)) + T(n)*(2*T(n+3) - 2*T(n+2) - 2*T(n+1) - T(n))
T(2n+1) = T(n)^2 + T(n+2)^2 + T(n+1)*(2*T(n+3) - 2*T(n+2) - T(n+1))
T(2n+2) = T(n+1)*(2*T(n) + T(n+1)) + T(n+2)*(2*T(n+3) - T(n+2))
T(2n+3) = T(n+1)^2 + T(n+3)^2 + T(n+2)*(2*T(n) + 2*T(n+1) + T(n+2))

有了这些，我们就可以实现"fast doubling"方法了。这是 Python 中的一个这样的实现，它对任意大小的整数的原生支持非常方便：

def tetranacci_by_doubling(n):
    if n >= 0:
        a, b, c, d = 0, 0, 0, 1 # T(0), T(1), T(2), T(3)
    else: # n < 0
        a, b, c, d = 1, 0, 0, 0 # T(-1), T(0), T(1), T(2)

    # unroll the last iteration to avoid computing unnecessary values.
    for i in reversed(range(1, abs(n).bit_length())):
        w = b*(2*c - b) + a*(2*(d - c - b) - a)
        x = a*a + c*c + b*(2*(d - c) - b)
        y = b*(2*a + b) + c*(2*d - c)
        z = b*b + d*d + c*(2*(a + b) + c)

        a, b, c, d = w, x, y, z

        if (n >> i) & 1 == 1:
            a, b, c, d = b, c, d, a + b + c + d

    if n & 1 == 0:
        return b*(2*c - b) + a*(2*(d - c - b) - a)  # w
    else: # n & 1 == 1
        return a*a + c*c + b*(2*(d - c) - b)        # x

def tetranacci(n):
    a, b, c, d = 0, 0, 0, 1 # T(0), T(1), T(2), T(3)
    # offset by 3 to reduce excess computation for large positive `n`
    n -= 3 

    if n >= 0:
        for _ in range(+n):
            a, b, c, d = b, c, d, a + b + c + d
    else: # n < 0
        for _ in range(-n):
            a, b, c, d = d - c - b - a, a, b, c

    return d

# sanity check
print(all(tetranacci_by_doubling(n) == tetranacci(n) for n in range(-1000, 1001)))

~~我希望根据 T(n-3),T(n-2),T(n-1),T(n) 将加倍公式调整为 T(2n-3),T(2n-2),T(2n-1),T(2n) 以略微减少大 n 的额外计算，但简化移位的公式很乏味。~~

更新

切换到迭代版本，因为我想出了如何使它以最少的重复干净地处理负面 n。最初，这是递归版本的唯一优势。
结合了多篇有关计算斐波那契数和卢卡斯数的论文中描述的技术——即在循环后手动执行最后的加倍步骤，以避免计算额外的不需要的值。这导致大约 40%-50% 的大 n 加速（>= 10^6)！这种优化也可以应用于递归版本。

上一次迭代的展开带来的加速非常有趣。这表明近一半的计算工作是在最后一步完成的。这是有道理的，因为当 n 加倍时，T(n) 中的位数（以及算术成本）大约加倍，我们知道 2^n ~= 2^0 + 2^1 + ... + 2^(n-1)。将优化应用于类似的 Fibonacci/Lucas 加倍算法会产生类似的约 40% 的加速——不过，如果您正在计算 Fibonacci/etc。模一些 64 位 M，我怀疑这种优化没有那么有价值。

Log(n) 中的四联数

Tetranacci Numbers in Log(n)

algorithm

runtime

matrix-multiplication

更新