fibonacci - 斐波那契矩阵

Question

为了计算 O(logn) 中的斐波那契数列，我们使用矩阵指数，因为该项
fn = fn-1 + fn-2是线性的，但是如果我们想找到的第 n 项需要什么矩阵

fn = fn-1 + fn-2 + a0 + a1*n + a2*n^2 + ... an*n^n
哪个是依赖多项式？？？
这里 a0,a1,... an 是常数

Answer 1

在此处查找使用公式 的 Erlang 中的实现 。它显示了很好的线性结果行为，因为O(M(n) log n)部分M(n)是大数字的指数。它在 2 秒内计算出一百万的 fib，其中结果有 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将以和Acc身份启动I等于。