Faster Fibonacci

fib.ml

(* To build and run: *)
(* ocamlfind ocamlopt nums.cmxa fib.ml -o fib && ./fib *)

open Big_int

let rec fib_naive n =
  if n < 1
  then failwith "undefined"
  else if n = 1 || n = 2
  then big_int_of_int 1
  else add_big_int (fib_naive (n - 1)) (fib_naive (n - 2))
;;

let fib_memo =
  let res = Hashtbl.create 16 in
  Hashtbl.add res 1 (big_int_of_int 1);
  Hashtbl.add res 2 (big_int_of_int 1);
  let rec fib n =
    if n < 1 then
      failwith "undefined";
    match Hashtbl.find res n with
    | resx ->
      resx
    | exception _ ->
      let resx = add_big_int (fib (n - 1)) (fib (n - 2)) in
      Hashtbl.add res n resx;
      resx
  in
  fib
;;

let fib_iter n =
  if n < 1 then
    failwith "undefined";
  let one = big_int_of_int 1 in
  if n = 1 || n = 2
  then
    one
  else
    let rec loop a b n =
      if n = 0
      then b
      else loop b (add_big_int a b) (n - 1)
    in
    loop one one (n - 2)
;;

let rec pow ~mult ~n x =
  if n < 1
  then
    failwith "undefined"
  else if n = 1
  then
    x
  else if n mod 2 = 0
  then
    let y = pow ~mult x ~n:(n / 2) in
    mult y y
  else
    let y = pow ~mult x ~n:(n / 2) in
    mult x (mult y y)
;;

type mat =
  { m00 : big_int; m01 : big_int;
    m10 : big_int;  m11 : big_int;
  }

let mat_mult a b =
  let ( * ) = mult_big_int in
  let ( + ) = add_big_int in
  { m00 = a.m00 * b.m00 + a.m01 * b.m10;
    m01 = a.m00 * b.m10 + a.m01 * b.m11;
    m10 = a.m10 * b.m00 + a.m11 * b.m10;
    m11 = a.m10 * b.m10 + a.m11 * b.m11;
  }
;;

let m_fib =
  let big = big_int_of_int in
  { m00 = big 1; m01 = big 1;
    m10 = big 1; m11 = big 0;
  }
;;

let fib_mat n =
  if n < 1 then
    failwith "undefined";
  let m = pow ~mult:mat_mult m_fib ~n in
  m.m01
;;

(* Printf.printf "%s\n" (string_of_big_int (fib_naive 1000));; *)
Printf.printf "%s\n" (string_of_big_int (fib_memo 1000));;
Printf.printf "%s\n" (string_of_big_int (fib_iter 1000));;
Printf.printf "%s\n" (string_of_big_int (fib_mat 1000));;

Makefile

run: fib
	./fib

fib: fib.ml
	ocamlfind ocamlopt nums.cmxa fib.ml -o fib

Blog post: Faster Fibonacci