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); // add to cache fibCache.Add(n, fn); 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); }

## No comments:

Post a Comment