详细说明见：http://www.cppblog.com/flyinghearts/archive/2010/08/02/118593.html

算法：
　　F(n+2) = F(n+1) + F(n)　　
   用归纳法可证明：F(n) = F(k)*F(n+1-k) + F(k-1)*F(n-k)
　　利用这两个公式可实现O(log n)。

unsigned fib_last4( unsigned num)
{
  if ( num == 0 ) return 0;
  const unsigned M=10000;
  unsigned ret=1,next=1,ret_=ret;
  unsigned flag=1, tt=num;
  while ( tt >>= 1) flag <<= 1;
  while ( flag >>= 1 ){
    if ( num & flag ){
      ret_ = ret * ret + next * next;
      next = (ret + ret + next) * next;
    } else {
      //多加一个M，避免 2*next-ret是负数，造成结果不对
      ret_ = (next + next + M - ret) * ret;
      next = ret * ret + next * next;
    }
    ret = ret_ % M;
    next = next % M;
  }
  return ret;
}

• Re:Fibonacci O(log n) 非矩阵算法 (772) ygl6188 2011-03-10 13:12:45