(* Function f : int -> int32 returns the n'th Fibonacci number
 * It uses ALGORITHM 1A: BINARY RECURSION
 *)
let rec f = function
  | 0 -> Int32.one
  | 1 -> Int32.one
  | x -> Int32.add (f(x-1)) (f(x-2));;
(* Function f_print : int -> 'a  prints the n'th Fibonacci number *)
let f_print n = Printf.printf "%dth Fibonacci number is %lu\n" n (f n);
                exit 0;;
f_print(46);;

(* Llist is a lazy evaluated infinite list as implemented by
 * Sebastien Furic on OCaml Mailing List
 *)
type 'a llist = LList of 'a * 'a llist Lazy.t | Empty ;;
let tl = function
  | Empty -> failwith "tl: empty list"
  | LList (_, lxs) -> Lazy.force lxs
let rec map2 f xs xs' = match xs, xs' with
  | Empty, Empty -> Empty
  | LList (x, lxs), LList (x', lxs') ->
      LList (f x x', lazy (map2 f (Lazy.force lxs) (Lazy.force lxs')))
  | Empty, LList _ | LList _, Empty -> invalid_arg "map2";;
let rec nth xs n = match xs, n with
  | Empty, _ -> failwith "nth"
  | LList (x, _), 0 -> x
  | LList (_, lxs), _ -> nth (Lazy.force lxs) (n - 1);;

(* Reading from the n'th position of the list fl returns n'th Fibonacci number
 * It uses ALGORITHM 2A-1: INFINITE LIST
 *)
let rec fl = LList (Big_int.unit_big_int,
			   lazy (LList (Big_int.unit_big_int,
				lazy (map2 ( Big_int.add_big_int ) fl (tl fl)))));;

(* Function f_print : int -> 'a  prints the n'th Fibonacci number *)
let f_print n = Printf.printf "%dth Fibonacci number is %s\n" n (Big_int.string_of_big_int(nth fl n));
                exit 0;;
f_print(160000);;

open Big_int
(* Function f returns the n'th Fibonacci number
 * It uses ALGORITHM 2B: SIMPLE RECURSION
 *)
let rec f ?(a=unit_big_int) ?(b=unit_big_int) n  =
    if n<2 then a else f ~a:(add_big_int a b) ~b:a (n-1);;
(* Function f_print : int -> 'a  prints the n'th Fibonacci number *)
let f_print n = Printf.printf "%dth Fibonacci number is %s\n" n (string_of_big_int(f n));
                exit 0;;
f_print(600000);;

open Big_int
(* Function f returns the n'th Fibonacci number
 * It uses ALGORITHM 2C: NON-RECURSIVE LOOP
 *)
let f n =
  let x1 = ref unit_big_int in
    let x2 = ref unit_big_int in
      let tmp = ref zero_big_int in
        for i = 1 to n do
           tmp := add_big_int !x1 !x2;
           x1 := !x2;
           x2 := !tmp;
        done;
!x1;;
(* Function f_print : int -> 'a  prints the n'th Fibonacci number *)
let f_print n = Printf.printf "%dth Fibonacci number is %s\n" n (string_of_big_int(f n));
                exit 0;;
f_print(600000);;

open Big_int
(* Function mm multiplies two 2x2 matrices presented as lists of four elements *)
let mm = function
    [a11;a12;a21;a22],[b11;b12;b21;b22] ->
        [add_big_int(mult_big_int a11 b11) (mult_big_int a12 b21);
         add_big_int(mult_big_int a11 b12) (mult_big_int a12 b22);
         add_big_int(mult_big_int a21 b11) (mult_big_int a22 b21);
         add_big_int(mult_big_int a21 b12) (mult_big_int a22 b22)]
    | _,_ -> [];;
(* Function mp raises matrix m into nth power *)
let rec mp(m,n) =
    if(n>1) then
        let a=mp(m,n/2) in
        if (n mod 2)=1 then mm(mm(a,a),m) else mm(a,a)
    else m;;
(* Function f returns the n'th Fibonacci number
 * It uses ALGORITHM 3A: MATRIX EQUATION
 *)
let f n =
    List.hd ( mp ([unit_big_int;unit_big_int;unit_big_int;zero_big_int], n) );;
(* Function f_print : int -> 'a  prints the n'th Fibonacci number *)
let f_print n = Printf.printf "%dth Fibonacci number is %s\n" n (string_of_big_int(f n));
                exit 0;;
f_print(1000000);;

open Big_int
(* Function f returns the n'th Fibonacci number
 * It uses ALGORITHM 3B: FAST RECURSION
 *)
let f n =
  let rec fl = function
    | 0
    | 1 -> (unit_big_int, unit_big_int)
    | 2 -> (big_int_of_int 2, unit_big_int)
    | n ->
        if (n mod 2) = 1 then
          let (k1,k2) = fl((n-1)/2)
	      in
           ( add_big_int (mult_big_int k1 (add_big_int k1 k2)) (mult_big_int k1 k2),
             add_big_int (square_big_int k1) (square_big_int k2))
        else
          let (l1,l2) = fl((n/2)-1)
	      in
           ( add_big_int (square_big_int (add_big_int l1 l2)) (square_big_int l1),
             add_big_int (mult_big_int l1 (add_big_int l1 l2)) (mult_big_int l1 l2))
in
  fst (fl n);;
(* Function f_print : int -> 'a  prints the n'th Fibonacci number *)
let f_print n = Printf.printf "%dth Fibonacci number is %s\n" n (string_of_big_int(f n));
                exit 0;;
f_print(1000000);;

(* Function f returns the n'th Fibonacci number
 * It uses ALGORITHM 3C: BINET'S FORMULA
 *)
let f n  =
   let phi = (1.+.sqrt(5.))/.2. in
     (phi**float(n+1) -. (1.-.phi)**float(n+1))/.sqrt(5.) ;;
(* Function f_print : int -> 'a  prints the n'th Fibonacci number *)
let f_print n = Printf.printf "%dth Fibonacci number is %.0f\n" n (f n);
                exit 0;;
f_print(69);;