斐波那契矩阵

Question

为了计算O(logn)中的fibonacci序列，我们使用矩阵指数，因为项

fn = fn-1 + fn-2是线性的，但是如果我们想要找到第n项，需要什么矩阵呢？

fn = fn-1 + fn-2 + a0 + a1*n + a2*n^2 + ... an*n^n

哪个是依赖于多项式的？

这里a0，a1，..。A是常量

Answer 1

在这里查找使用公式的implementation in Erlang

。它显示了良好的线性结果行为，因为在O(M(n) log n)部件中，M(n)对于大数是指数型的。它在2s内计算一百万的fib，其中result有208988位数字。诀窍是你可以使用(尾部)递归公式计算O(log n)乘法中的求幂(尾部意味着使用O(1)空间，当使用适当的编译器或重写循环时)：

% compute X^N
power(X, N) when is_integer(N), N >= 0 ->
    power(N, X, 1).

power(0, _, Acc) ->
    Acc;
power(N, X, Acc) ->
    if N rem 2 =:= 1 ->
            power(N - 1,   X,     Acc * X);
        true ->
            power(N div 2, X * X, Acc)
    end.

其中X和Acc替换为矩阵。将使用以下命令启动X

并且identity为I的Acc等于

。