Instantly share code, notes, and snippets.

scvalex/Makefile Last active Aug 29, 2015

Faster Fibonacci
 (* 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));;
 run: fib ./fib fib: fib.ml ocamlfind ocamlopt nums.cmxa fib.ml -o fib
Owner Author

scvalex commented Jan 10, 2015

 Blog post: Faster Fibonacci