(* versão com memoização baseada numa tabela de hash, e uso dos big_ints *)

(*compilation:  ocamlopt nums.cmxa perrin_hash.ml -o perrin_hash *)

open Big_int
open Hashtbl
  
let zero = big_int_of_int 0;;
let one = big_int_of_int 1;;
let two = big_int_of_int 2 ;;
let three = big_int_of_int 3;;
let ( ++ ) = add_big_int;;

let ht = create 97;;

let rec perrin n = 
 match n with
 |0 -> three
 |1 -> zero
 |2 -> two
 | m when m<0 ->  failwith "Argumento inválido"
 |_ -> try
         find ht n
       with
         Not_found ->
           let n2 = perrin (n-2) in
           let n3 = perrin (n-3) in
           let res = (n2 ++ n3) in
             (Hashtbl.add ht n res; res)
         
let () = print_endline (string_of_big_int (perrin (read_int ())))