# 雁过无痕

 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)  编辑 收藏 引用 所属分类: 算法