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