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