Write Use OCAML language a function to compute fibonacci numbers (in the sequenc

Question

Write Use OCAML language a function to compute fibonacci numbers (in the sequence 0, 1, 1, 2, 3, 5, ... where each number is the sum of the previous two numbers on the list). Use pattern matching but no if/then/else statements. Use a tail recursive solution to make sure the function doesn't take exponential time. Call your function fibonacci. Test it by computing the 44th fibonacci number. What happens when you try to compute larger fibonacci numbers? Why? Indicate the answer in a comment in your code.

Explanation / Answer

* This program calculates the nth fibonacci number * using algorithm 3B: fast recursion * * compiled: ocamlopt -ccopt -march=native -o f3b nums.cmxa f3b.ml * executed: ./f3b n *) open Num (* calculate a pair of fibonacci numbers according to * the recurrent relationship: * F(2n-1) = F(n-1)^2 + F(n)^2 * F(2n) = (2F(n-1) + F(n))F(n) * * in this function, k1 = F(n-1), k2 = F(n), k3 = F(n+1) *) let rec f = function | n when n invalid_arg "negative argument" | 0 -> (Int 0, Int 0) | 1 -> (Int 1, Int 0) | n -> let (k2, k1) = f (n/2) in let k3 = k2 +/ k1 in let k2s = k2 */ k2 in let k1s = k1 */ k1 in let k3s = k3 */ k3 in if (n mod 2) = 0 then (k1+/k3)*/k2, k1s+/k2s else k3s+/k2s, (k1+/k3)*/k2 (* entry point *) let _ = (* read the integer argument from command line *) let n = try int_of_string Sys.argv.(1) with _ -> invalid_arg "Usage: f3b " in (* calculate f(n) *) let answer = (if n n) (fst (f (abs n))) in (* output *) Printf.printf "%dth Fibonacci number is %s " n (string_of_num answer)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.