Skip to content

Instantly share code, notes, and snippets.

@scvalex scvalex/Makefile
Last active Aug 29, 2015

Embed
What would you like to do?
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
@scvalex

This comment has been minimized.

Copy link
Owner Author

commented Jan 10, 2015

Blog post: Faster Fibonacci

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.