Speeding up Fibonacci computation using Caching

Dynamic programming is essentially a tradeoff of space for time. Repeatedly re-computing a given quantity is harmless unless the time spent doing so becomes a bottleneck in the performance. In this case we should better be storing/caching the previously calculated values and looking them up when needed instead of re-computing.

Think about computing a Fibonacci number by recursion:

Fn = Fn-1 + Fn-2  (with F0 = 0, F1 = 1)

Lets explore the two different solutions. one without the caching and other with caching.

Example 1: code without the knowledge of the previous calculated values (caching/table lookup):

[cpp]

long Fib(int n)

{

if(n == 0) return 0;
if(n == 1 ) return 1;

return Fib(n-1) + Fib(n-2);

}

[/cpp]

Example 2: code with caching or table lookup.

In this example, we will first check if the Fib(n) already exists in the lookup table. If exists then we will use it else we will compute and store the computed result in the lookup table for future reference. Caches/Lookup table is useful here as the value 'Fib(n)' for a given number 'n' is always constant e.g. Fib(3) = 2 always.

[cpp]

#define UNKNOWN -1 /*for empty cell or item not found*/
long Cache[MAX]; /*we use table/array here however building
HashTable would be more efficient in space however arrays are
efficient in lookup time*/
long Fib(int n)
{
int i;

Cache[0] = 0;
Cache[1] = 1;

for(i=2; i< n; i++)  Cache[i] = UNKNOWN;

return FibCache(n);

}

long FibCache(int n)
{

if(Cache[n] == UNKNOWN)
Cache[n] = FibCache(n-1) + FinCache(n-2);

return Cache[n];

}

[/cpp]

Why Example 2 is faster than Example 1?

The first example always calculates Fib(i) whenever it encounters in the recursion cycle. e.g.  in calculation of Fib(6), we need to calculate Fib(5) and Fib(4). Fib(5) again needs to calculate Fib(4). So here we are calculating Fib(4) twice.

If you look at Example 2, we have a lookup array created which keeps track of previously calculated value at a specified index in the array. e.g. Fib(4) will be stored in Cache[4] with value 3. So when the program goes to calculate the Fib(5), it checks if Fib(4) is already exists in the lookup table. if yes then it uses and proceeds ahead without investing time in recalculating it.