Fibonacci Number
フィボナッチ数
Program
分割統治法によるフィボナッチ数生成プログラム.
long Divide_Conquer_Fib(long n) {
long i, h, j, k;
i = h = 1;
j = k = 0;
while(n > 0) {
if(n % 2 == 1) { // if n is odd
t = j * h;
j = i * h + j * k + t;
i = i * k + t;
}
t = h * h;
h = 2 * k * h + t;
k = k * k + t;
n = (long)n / 2;
}
return j;
}