Why does it take a long time to calculate the Fibonacci number?
I started learning Ocaml a few days ago. I tried to make a fibonakos numbers program:
let rec fib a=
if a=1||a=2 then 1 else fib(a-1)+fib(a-2);;
This code is not optimal as I don't know how to handle exceptions. But at the moment, if I try to calculate fib 50 or fib 100, then the computer must spend a lot of time evaluating. I'm wondering why, as Ocaml is supposed to be very fast and adding numbers is obviously a linear time problem. If I paste this code into "Try Ocaml" ( http://try.ocamlpro.com/ ) then the whole site freezes when I execute phile 50.
Sorry if the level of the question is too low.
source to share
Because this is a poster example for poor use of recursion. It should be forbidden to use this as an example for the grace of recursion, because this is indeed a completely inelegant wrt machine.
For each call, fib
you get two more calls fib
:
depth | call tree
------+------------------------------------------------------------------------
1 | fib-----+
| | \
2 | fib fib
| | \ | \
3 | fib fib fib fib
| ....
4 | fib fib fib fib fib fib fib fib
| ....
5 | fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| ....
6 | fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| ....
7 | fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| ....
8 | fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| ....
9 | fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
| fib fib fib fib fib fib fib fib
What you have is not an OCaml problem, but rather a computation / algorithm problem. Fibonacci numbers are a good example for when "simple" recursion is not desired. It looks simple and elegant, but it denies reality.
So, implement this as a loop and your problem goes away.
Complexity
This is a good question to indicate computational complexity ( Big O Notation ). Your implementation has exponential complexity O (2 n ), i.e. The time it takes to run your algorithm grows exponentially wrt per input. The summation loop will run in O (n) i.e. The time required to solve the problem grows linearly wrt at the entrance.
See also Fibonacci series algorithm function .
source to share
phresnel is absolutely correct that the usual recursive definition of the Fibonacci function is an extremely poor way of calculating it. It's easy to see at least one recursive call in there for every time you want to add 1 to the result. Since the Fibonacci function is exponential (roughly 1.6 ^ n), you must make an exponential number of recursive calls.
Here's a fast enough recursive Fibonacci function:
let fib n =
let rec ifib i a b =
if i = n then b
else ifib (i + 1) b (a + b)
in
ifib 0 0 1
source to share
And for completeness, here is the logarithmic version of fibonacci:
(* exponentiation by squaring *)
let rec pow e ( * ) x = function
| 0 -> e
| 1 -> x
| n ->
let r = pow e ( * ) x (n/2) in
if n mod 2 = 0 then r * r else r * r * x
(* matrix product *)
let ( ** ) a b =
assert
(Array.length a = Array.length a.(0)
&& Array.length b = Array.length b.(0)
&& Array.length a = Array.length b);
let n = Array.length a in
let c = Array.make_matrix n n 0 in
for i = 0 to n-1 do
for j = 0 to n-1 do
for k = 0 to n-1 do
c.(i).(j) <- c.(i).(j) + a.(i).(k) * b.(k).(j)
done;
done;
done;
c
let id = [|[|1; 0|]; [|0; 1|]|]
(* companion matrix for fibonacci *)
let f0 = [|[|0; 1|]; [|1; 1|]|]
let fibo n = (pow id ( ** ) f0 n).(1).(1)
It works by taking a companion matrix and calculating its cardinality.
source to share
You wrote the notorious two-recursive Fibonacci function. Since there are two recursive calls in each call, the total number of calls grows exponentially with the number of levels of recursion.
The usual way to deal with this is to either rewrite the function to calculate in such a way that it does not require recursion (for Fibonacci, you can start at 1 and go up, instead of going to a-1
and a-2
, so that you already have earlier values in the series when you need them) or use memoization to cache the values so you never need to compute the same value more than once. Once it has fib 23
been calculated, any subsequent call to it simply pulls it out of the cache, rather than calculating it again.
However, the Fibonacci sequence also has a closed form (search for the "closed form" at this link), which is related to the & Phi ;, the golden ratio:
let round f =
int_of_float (f +. 0.5)
let phi = (1. +. (sqrt 5.)) /. 2.
let fibf n =
(phi ** n) /. (sqrt 5.)
let fib n =
round (fibf n)
This implementation computes the Fibonacci sequence value directly, without iteration or recursion. This, however, is limited to floating point precision. This would be unacceptable as a substitute for an iterative solution that was intended, for example, to continue to work in the area of bonuses.
source to share