雁過無痕

 

import std.stdio : writef;

 

uint fib_matrix(uint num) // 矩陣法求fibonacci數(shù)

{

 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()

{

 

}