如何快速得到fibonnacci数列的某一项? 该帖改编自HAKMEM:
http://www.inwap.com/pdp10/hbaker/hakmem/recurrence.html#item12

定义一个二元数数乘法:
(A,B) (C,D) = (A C + A D + B C, A C + B D).
我们注意到 (A,B) (1,0) = (A + B, A), 这就是fibonacci的迭代公式.因此有 (1,0)^N = (FIB(N), FIB(N-1)). 这预示我们可以在logN的时间内得到数列的第N项.

例如:FIB(1) => (1,0)^1=(1,0);
FIB(2) => (1,0)^2=(1,1); 
FIB(4) => (1,0)^4=(3,2);
FIB(5) => (1,0)^1 * (1,0)^4=(1,0)*(3,2)=(5,3);
...

下面是实现代码:
#include <iostream>
#include <cstdlib>

using namespace std;

struct Pair {
    int a;
    int b;
};

Pair transform (const Pair &A, const Pair &B)
{
    if (A.a == 0)
        return B;
    Pair tmp;
    tmp.a = A.a*B.a + A.a*B.b + A.b*B.a;
    tmp.b = A.a*B.a + A.b*B.b;

    return tmp;
}

int fast_fibonacci_transform (int n)
{
    assert (n > 0);
    Pair now = {1, 0}, sum = {0, 0};

    if (n & 1) sum = now;
    n >>= 1;
    while (n) {
        now = transform (now, now);
        if (n & 1)
            sum = transform (sum, now);
        n >>= 1;
    }

    return sum.a;
}

int main ()
{
    int n = 47;
    for (int i = 1; i <= n; ++i)
        cout << fast_fibonacci_transform (i) << ' ';
    cout << endl;
    system ("pause");
    return 0;
}

输出:
1 1 2 3 5 8 13...