I'm not sure if I still love Fibonacci, but my code is getting better. How much better?

Technically, this is a follow up to these two questions, but I have taken a radically different approach.

• Everybody Loves Fibonacci

• Does everyone still love Fibonacci

I finally allowed myself to be convinced that it should not be as object oriented as I wanted it to be. I opted instead to return any given \$F_n\$ as quickly as possible. I used a Dictionary to cache previous results, always looking in the dictionary for the requested value before doing any other processing.

So, hit me. I think I did pretty good this time around. What do you think?

Note: I'm avoiding the naive recursive solution because it is far slower than an iterative algorithm.

Fibonacci

```
using System;
using System.Collections.Generic;
using System.Numerics;

namespace Challenges
{
class Fibonacci
{
private Dictionary dictionary;

public Fibonacci()
{
dictionary = new Dictionary();
}

public BigInteger Calculate(int ordinalPosition)
{
BigInteger returnValue;
BigInteger previous1;
BigInteger previous2;

//first try to get it from the dictionary
if (dictionary.TryGetValue(ordinalPosition, out returnValue))
{
return returnValue;
}

// Fn where n 2)
{
//start at the next missing fibonacci number
for (int i = dictionary.Count; i <= ordinalPosition; i++)
{
dictionary.TryGetValue(dictionary.Count - 1, out previous1);
dictionary.TryGetValue(dictionary.Count - 2, out previous2);
returnValue = previous1 + previous2;
dictionary.Add(i, returnValue);
}
return returnValue;
}

//If all else fails, start at the beginning.
Fibonacci fib = new Fibonacci();
for (int i = 0; i <= ordinalPosition; i++)

A Dictionary is the wrong data structure to use for memoization here. An ArrayList A List would be more appropriate. The reason is that the entries are not independent, but rather sequential: it will remember all entries from the 0th to some maximum. There's not much point to hashing when a simple array lookup will do.

When a value is not in the cache, there's no need to start from the beginning. You can continue from the last known value, whose ordinalPosition corresponds to dictionary.Count - 1.

By the way, dictionary is just about the least informative name possible for a Dictionary. I suggest something more meaningful, such as memo, since you are using it for memoization.

To prime the cache, use a static constructor. Priming the cache at class-loading time, do it in the constructor, which avoids having to conditionally go through those special cases every time you call Calculate.

StackExchange Code Review Q#56899, answer score: 7