## Tuesday, January 6, 2009

### Fibonacci and Big-Oh reduction

I was asked to write some C# to implement a Fibonacci sequence, which falls into two parts: 1) generate a single number in the sequence, 2) generating the whole sequence.

Note that most examples of this sequence generator have a nasty bug in them. Most examples use the int data type, whilst this code uses the long data type, otherwise this function overflows around n=47.

The naive way to implement this is recursively:
```  /// <summary>
/// slow version of fib calc for testing - warning
/// runs in O(1.618..n)
/// </summary>
internal long Fibonacci(int n)
{
if (n < 2)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
```

And a more optimal approach is:
```  /// <summary>
/// returns the Fibonacci number for N
/// </summary>
public long Fibonacci(int n)
{
// returns N where n < 2, for higher values of N
// avoids recursive solution by keeping track
// of previous results

long fn = 0;

if (n < 0) // offset must be positive
throw new NotSupportedException("Fibonacci sequence offset must be positive");
else if (n < 2) // returns N where N < 2
fn = n;
else // use caching technique for higher values of N
{
long fnMinusTwo = 0;
long fnMinusOne = 1;

for (long ni = 2; ni <= n; ni++)
{
// effectively: fn = Fibonacci(n - 1) + Fibonacci(n - 2)
fn = fnMinusOne + fnMinusTwo;

fnMinusTwo = fnMinusOne;
fnMinusOne = fn;
}
}

return fn;
}
```
The latter approach is much more efficient O(n) vs O(1.618..n). However its not as simple as the former. Another approach is to take the former solution and use a local cache:
```  /// <summary>
/// caching version of fib calc
/// </summary>
Dictionary<int, long> fibCache = new Dictionary<int, long>();
internal long Fibonacci(int n)
{
long fn = 0;

// use value from cache if already calculated
if (fibCache.ContainsKey(n))
return fibCache[n];

// not cached, need to work it out
if (n < 2)
fn = n;
else
fn = Fibonacci(n - 1) + Fibonacci(n - 2);

return fn;
}
```
This gives us an O(n) runtime with a reasonably simple implementation. This is of course the classic trade-off of time vs. space - we have increased space used (the dictionary) to decrease time.

Finally we want to generate the whole sequence, which we can do in a lazy evaluation way using the yield keyword:
```  /// <summary>
/// returns the first N items in the Fibonacci sequence
/// </summary>
public static IEnumerable<long> FibonacciSequence(int n)
{
for (int fn = 0; fn < n; fn++)
yield return Fibonacci(fn);
}
```