回归--快速幂与斐波那契数列

在假期里重新回归算法的学习，首先在这里简要写一下利用快速幂来求得斐波那契序列的原理。
具体的代码和解释百度里都有涉及，在这里只写一下自己的推论过程。
由于使用递归算法会浪费太多的时间与空间，所以在这里使用矩阵的方法来实现计算。
学过代数的人可以看出，下面这个式子是成立的：

而这个式子可以不断递归，得到下面的式子：

由于Fib[0]与Fib[1]是已知，那么只需求矩阵的次幂就可以了。
在这里使用到的就是快速幂，关于快速幂的解释看这里：
http://baike.baidu.com/link?url=dbyx1Lo9P_Ca2cRdKuttAobLhFrmlyfGuCYn1MnzHvOVu-QwilkS3guqyxSZNXIWxlW8s9IIPAgf2_swv093Hq
简单来说就是 使用位运算来快速求得一个数的 多少个次幂。
简单的位运算有&，|，<<，>>，~，^等，具体使用方法不再赘述。
在这里使用的是快速幂的非递归算法。
当求一个数a的n次幂的时候，需要将该数a相乘n次，那么时间复杂度为n，为了减小该时间复杂度，需要减小n。
已知任意一个数k都可以写成2ⁿ⁰⁺²n1+2^n2……形式，那么有：
假设n=11，那么:

我们想要求a的11次幂，只需将11的2进制数从低位开始取，每次取一位，将该位数乘2的相应位数（从一开始取位累加）次幂，将a取该数的次幂再累乘即可。
在这里截取网上的相关代码：

int Qpow(int a,int n)
{
    int ans = 1;
    while(n)
    {
        if(n&1) ans *= a;
        a *= a;
        n >>= 1;
    }
    return ans;
}

而斐波那契数列的求取需要求的是一个矩阵的幂，故需要将函数中的所有乘法替换为22矩阵的乘法，然后将a与ans均替换为22的矩阵，矩阵相乘的函数可根据代数知识获得：

matrix multi(matrix a, matrix b)//matrix是2*2的矩阵类
{
    matrix tmp;
    for(int i = 0; i < 2; ++i)
    {
        for(int j = 0; j < 2; ++j)
        {
            tmp.m[i][j] = 0;
            for(int k = 0; k < 2; ++k)
                tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) ;
        }
    }
    return tmp;
}

替换后的快速幂函数表示为：

int fast_mod(int n)  //a与ans都是2*2的矩阵类型：matrix
{
    a.m[0][0] =a.m[0][1] = a.m[1][0] = 1;
    a.m[1][1] = 0;      //初始矩阵的值
    ans.m[0][0] = ans.m[1][1] = 1;  // ans 初始化为单位矩阵 
    ans.m[0][1] = ans.m[1][0] = 0;
    while(n)
    {
        if(n & 1)  
        ans = multi(ans, a);
        a = multi(a, a);
        n >>= 1;
    }
    return ans.m[0][1];
}

如果需要求某个斐波那契数取数b的模，那么根据代数知识，矩阵的每个数都需要求得该数的模，且每次相乘都需取模，则在矩阵相乘的函数中每次相乘后取一次模即可。
位置代码如下：

for(int k = 0; k < 2; ++k)
tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % b;//b是要取的模