fib(n) = fib(n-1) + fib(n-2); fib(1) = fib(0) = 1

This would typically be implemented in the venerable C language as:

unsigned long long fib(int n) { return n == 0 || n == 1 ? 1 : fib(n-1) + fib(n-2); }The problem with this implementation is that the performance is atrocious.

`The reason is that each higher number needs geometrically increasing number of recursive invocations:`

$ time ./fib -r 40 165580141 real 0m18.263s user 0m18.262s sys 0m0.002s

fib(0) = 1 call fib(1) = 1 call fib(2) = 3 calls fib(3) = 5 calls fib(4) = 9 calls fib(5) = 15 calls fib(6) = 25 calls fib(7) = 41 calls fib(8) = 67 calls fib(9) = 109 calls fib(10)=177 calls .... fib(40) = 331160281 callsCuriously, the number of calls for fib(n) can be defined as:

fib_calls(n) = 1 + fib_calls(n-1) + fib_calls(n-2); fib_calls(1) = fib_calls(0) = 1The performance problem is addressed by rewriting the function to work iteratively:

`This gives a remarkable boost in performance:`

unsigned long long iterative_fib(int n) { register unsigned long long n1 = 0, n2 = 1, tmp; int i = 0; for(i = 0 ; i < n; i++) { tmp = n2; n2 = n2 + n1; n1 = tmp; } return n2; }

`Another way to get around the performance problem is to use caching with the recursive algorithm:`

$ time ./fib -i 40 165580141 real 0m0.003s user 0m0.001s sys 0m0.002s

`Performance is similar to that of the iterative version:`

static unsigned long long cache[100]; unsigned long long cached_fib(int n) { if(cache[n]) return cache[n]; return n == 0 || n == 1 ? 1 : (cache[n] = cached_fib(n-1)+cached_fib(n-2)); }

`However, in a program that calls the fibonacci function numerous times, the cached recursive version would work on an average, faster than the iterative verion. The flip side is that caching uses up memory. After a certain threshold, the system starts swapping to disk and performance degrades rapidly. So you really want to select good algorithms wherever possible and save caching for operations that simply have to be cached such as those involving disk or network IO.`

$ time ./fib -c 40 165580141 real 0m0.003s user 0m0.000s sys 0m0.003s

## No comments:

Post a Comment