let ht = Hashtbl.create 100;;

(* Fibonacci com memoização com base numa tabela de hash
   memoização: capacitar uma função com uma memória dos calculos que já fez. 
   Nunca calcula duas vezes o mesmo valor. 
   Se já foi calculado, devolve directamente o valor previamente calculado.
   Se não foi calculado, calcula-se, grava-se na "memória" e devolve-se o 
   valor propriamente dito
 *)
let rec fibt n = 
 if n<0 then failwith "Input Negativo" else 
  try Hashtbl.find ht n 
  with Not_found -> 
    if n <= 1 then (Hashtbl.add ht n 1; 1)
    else let valor = fibt (n-1) + fibt (n-2) in 
             (Hashtbl.add ht n valor;valor)
    


let () = Printf.printf "%d\n"  (let x = int_of_string Sys.argv.(1) in
                        try fibt x
                        with Failure _ -> fibt (- x))
(*
$ time fib_memo 100010
4039261411255876802

real        0m0.052s
user        0m0.039s
sys        0m0.009s

$ time fib_memo 10000
-83367563645688771

real        0m0.013s
user        0m0.005s
sys        0m0.006s

Temos aqui um belo integer overflow!
isso deixa também suspeitar (com razão) que o resultado anterior está errado!
*)

This document was generated using caml2html