Fast-Doubling Fibonacci with Modular Arithmetic

Reported in interviews at Barclays Citadel Jump Trading

Problem statement

The standard recursive Fibonacci computation is $O(n)$ time. A much faster approach uses the fast-doubling identities to compute $F_n$ in $O(\log n)$ time.

Part 1. Implement a function that returns the pair $(F_n, F_{n+1})$ using the fast-doubling recurrences: $$F_{2k} = F_k(2F_{k+1} - F_k), \quad F_{2k+1} = F_k^2 + F_{k+1}^2$$ Your implementation should run in $O(\log n)$ time and $O(1)$ extra space (use an iterative or tail-recursive approach, not naive recursion).

Part 2. Extend your solution to compute $F_n \bmod M$ for arbitrary integer $M \geq 2$ (including non-prime $M$), without overflow.

Constraints:

  • $0 \leq n \leq 10^{18}$
  • $2 \leq M \leq 10^9$
  • Use 64-bit integers; intermediate products may overflow if not handled carefully.

Examples:

  • $n = 0$: return $(F_0, F_1) = (0, 1)$
  • $n = 7$: return $(F_7, F_8) = (13, 21)$
  • $n = 10$, $M = 7$: $F_{10} = 55$, so $F_{10} \bmod 7 = 6$
Show hint

Is there a way to jump from index $k$ to index $2k$ in one step, the way fast exponentiation squares?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems