雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::

 

import std.stdio : writef;

 

uint fib_matrix(uint num) // 矩阵法求fibonacci数

{

 if (num <= 1) return num;

 --num;

 uint ret = 1, next = 1;

 for (uint a = 1, b = 0; num != 0; num >>= 1) {

    if (num & 1) {

       auto tmp = next;

       next = (a + b) * next + a * ret;

       ret = a * tmp + b * ret;

      }

      auto tmp = a;

      a = a * (a + 2 * b);

      b = b * b + tmp * tmp;

 }

 return ret;

}

 

uint fib(uint num)

{

 if (num <= 1) return num;

 

 uint left_most_one = num; //小等于num的最大2的k次幂

 for (uint value = num; value &= (value - 1); ) left_most_one = value;

 

 uint ret = 1, next = 1;

 while (left_most_one >>= 1) {

    if (num & left_most_one) {

       auto tmp = ret;

      ret = ret * ret + next * next;

      next = (tmp * 2 + next) * next;

    } else {

       auto tmp = ret;

      ret = (next * 2 - ret) * ret;

      next = tmp * tmp + next * next;

    }

 }

 return ret;

}

 

uint fib_basic(uint num)

{

 if (num <= 1) return num;

 uint prev = 0, current = 1;

 for (uint i = 2; i <= num; ++i) {

    auto tmp = prev;

    prev = current;

    current += tmp;

 }

 return current;

}

 

unittest {

 foreach (i; 0 .. 48) {

    auto a = fib_basic(i), b = fib_matrix(i), c = fib(i);

    if (a != b || a != c)

      writef("%s %s %s %s\n", i, a, b, c);

 } 

}

 

void main()

{

 

}

posted on 2011-07-20 23:30 flyinghearts 阅读(738) 评论(0)  编辑 收藏 引用 所属分类: 算法

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理