(* versão com memoização baseada num vector (associativo), e uso dos nums (em lugar dos big_ints) *)

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

open Num

let n = read_int()

(* cria-se a tabela de memoização: 
   memo.(i) -> i-esimo elemento da sequência, se tiver sido já calculado,
               -1 senão *)
let memo = Array.make (n+1) (Int (-1))
let () = (memo.(0) <- (Int 3); memo.(1) <- (Int 0); memo.(2) <-  (Int 2))

let rec perrin n = 
  match n with
  | 0 | 1 | 2   -> memo.(n)
  | n when n<0  ->  failwith "Argumento inválido"
  | n           -> let res = memo.(n) in
                     if res >= Int 0 then res
                     else
                       let n2 = perrin (n-2) in
                       let n3 = perrin (n-3) in
                       let v = (n2 +/ n3) in
                       let () = memo.(n) <- v in
                         v

let () = print_endline (string_of_num (perrin n))