c++ - 斐波那契 - 分而治之的算法

Question

#include <iostream>
using namespace std;

int main() {
    int i=1;
    int j=0;
    int k=0;
    int h=1;
    int t=0;
    int n;
    cin>>n;

    while (n) {
        if (n%2) {
            t=j*h;
            j=i*h+j*k+t;
            i=ik+t;
        }

        t=h*h;
        h=2*k*h+t;
        k=k*k+t;
        n=n/2;
    }

    cout<<j;
    return 0;
}

这是我在互联网上找到的最快的斐波那契算法。我理解的其他算法，但这对我来说没有任何意义。

我看不出该算法与矩阵乘法或平方求幂有何关系。有人可以解释吗？

Answer 1

这是计算斐波那契数的标准矩阵方法。变量 h、i、j 和 k 是矩阵的四个元素。矩阵算术以“手写”形式写出。

Answer 2

矩阵解是取矩阵

1 1
0 1

并将其提高到等于您想要的斐波那契数的幂。您可以使用 log(n) 步骤来做到这一点。您使用幂的二进制格式。在每一步中，您将矩阵与自身相乘（相当于将指数乘以 2），如果该位为 1（相当于将 1 加到指数），则与原始矩阵相乘。

现在再次检查代码。变量对矩阵中的 4 个单元格进行编码，并且有一些乘法逻辑的内联，但它仍然是相同的。