Fibonacci Computation — Matrix vs Doubling

Fast doubling

long[] fibDoubling(long n) {
  if (n == 0) return new long[]{0, 1};
  long[] r = fibDoubling(n / 2);
  long c = r[0] * (2 * r[1] - r[0]);
  long d = r[0] * r[0] + r[1] * r[1];
  return (n & 1) == 0 ? new long[]{c, d} : new long[]{d, c + d};
}

Matrix power

[[1,1],[1,0]]^n = [[F_{n+1}, F_n],[F_n, F_{n-1}]]. Modular power gives F_n.

Complexity

Both O(log n) multiplications. Fast doubling ~30% faster in practice.

Mod arithmetic

F_n mod m: use modular version. Pisano period: F_n mod m periodic with period ≤ 6m.