let rec fib_pair n =
  if n = 0 then (0, 1)
  else
    let (a, b) = fib_pair (n / 2) in
    let c = a * (2 * b - a) in
    let d = a * a + b * b in
    if n mod 2 = 0 then (c, d)
    else (d, c + d)

let fib n = let (f, _) = fib_pair n in f

;;

fib 40
