(* versão matricial, e uso de representação numérica de precisão arbitrária (num, em vez de big_int)

/      \  n   /   \    /       \
| 0 1 0 |     | 3 |    | P(n)  |
| 0 0 1 |  X  | 0 |  = | P(n+1)| 
| 1 1 0 |     | 2 |    | P(n+2)|
\       /     \   /     \      /

*)


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

open Array
open Num
       
let m = make_matrix 3 3 (Int 0)
let () = (m.(0).(1) <- (Int 1);  m.(1).(2) <- (Int 1);  m.(2).(0) <- (Int 1); m.(2).(1) <- (Int 1))

(*  multiplicação de matrizes 3 por 3*)
let ( +*+ ) a b =
  let m = make_matrix 3 3 (Int 0) in
  let () = m.(0).(0) <-  a.(0).(0) */ b.(0).(0) +/ a.(0).(1) */ b.(1).(0) +/  a.(0).(2) */ b.(2).(0);
           m.(0).(1) <-  a.(0).(0) */ b.(0).(1) +/ a.(0).(1) */ b.(1).(1) +/  a.(0).(2) */ b.(2).(1) ;
           m.(0).(2) <-  a.(0).(0) */ b.(0).(2) +/ a.(0).(1) */ b.(1).(2) +/  a.(0).(2) */ b.(2).(2) ;
           m.(1).(0) <-  a.(1).(0) */ b.(0).(0) +/ a.(1).(1) */ b.(1).(0) +/  a.(1).(2) */ b.(2).(0) ;
           m.(1).(1) <-  a.(1).(0) */ b.(0).(1) +/ a.(1).(1) */ b.(1).(1) +/  a.(1).(2) */ b.(2).(1) ;
           m.(1).(2) <-  a.(1).(0) */ b.(0).(2) +/ a.(1).(1) */ b.(1).(2) +/  a.(1).(2) */ b.(2).(2) ;
           m.(2).(0) <-  a.(2).(0) */ b.(0).(0) +/ a.(2).(1) */ b.(1).(0) +/  a.(2).(2) */ b.(2).(0) ;
           m.(2).(1) <-  a.(2).(0) */ b.(0).(1) +/ a.(2).(1) */ b.(1).(1) +/  a.(2).(2) */ b.(2).(1) ;
           m.(2).(2) <-  a.(2).(0) */ b.(0).(2) +/ a.(2).(1) */ b.(1).(2) +/  a.(2).(2) */ b.(2).(2) in
  m;;

(* exponenciação *rápida* de matrizes: M^n *)
let rec ( +^+ ) a = function
  0 -> [|[|(Int 1);(Int 1);(Int 1)|];[|(Int 1);(Int 1);(Int 1)|];[|(Int 1);(Int 1);(Int 1)|]|]
  | 1 -> a
  | n  ->let m =  a +^+ (n/2) in
    if  (n mod 2) = 0 then  m +*+ m else  a +*+ (m +*+ m)
     
let perrin n =
  if n<0 then  failwith "Argumento inválido"
  else
    let mm = m +^+ n in
    mm.(0).(0) */ (Int 3) +/ mm.(0).(2) */ (Int 2);;

let () = print_endline (string_of_num (perrin (read_int ())))