open Num

(* utilizamos a biblioteca Nums para uma aritmética de precisão arbitrária
   compilação:
      ocamltop nums.cmxa fib_large.ml 
ou    ocamlc nums.cma fib_large.ml 
 *)

(* Multiplicação de matrizes 2*2.
   Pequena optimização: na matriz quadrada em uso no calculo da 
   sequencia de fibonacci, o segundo elemento é sempre igual ao
   terceiro.
   Usamos este facto para dispensar um destes dois elementos.
*) 
let mul (a,b,c) (d,e,f) =
  (a*/d +/ b*/e, a*/e +/ b*/f, b*/e +/ c*/f)
 
let rec pow a n =
  if n=0 then (Int 1, Int 0, Int 1) (*ID matrix*)
  else
    if n=1 then a else
      let b = pow a (n/2) in
      if (n mod 2) = 0 then mul b b else mul a (mul b b)
          
let fib n =  let (x,_,_) = if n<0 then failwith "Input Negativo" 
                           else (pow (Int 1, Int 1, Int 0) n) 
             in x
let () =  
  let n = int_of_string Sys.argv.(1) in 
  Printf.printf "fib %d = %s\n" n (string_of_num (fib n))

This document was generated using caml2html