* Fibonacci Number [#v2be28fe]

''フィボナッチ数''

#contents

** Program [#bdd36bc4]
分割統治法によるフィボナッチ数生成プログラム.

#code(c){{
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;
}
}}