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

Question

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

1. Everybody Loves Fibonacci
2. 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<int, BigInteger> dictionary;

        public Fibonacci()
        {
            dictionary = new Dictionary<int, BigInteger>();
        }

        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 < 0 doesn't make sense
            if (ordinalPosition < 0)
            {
                throw new ArgumentOutOfRangeException("OrdinalPosition", "Can't calculate Fn when n is less than zero.");
            }

            //Handle special cases of n == 0,1, or 2 (Priming the function).
            if (ordinalPosition == 0)
            {
                dictionary.Add(ordinalPosition, 0);
                return 0;
            }

            if (ordinalPosition == 1 || ordinalPosition == 2)
            {
                dictionary.Add(ordinalPosition, 1);
                return 1;
            }

            //If we already have the previous ordinalPosition, use that value to calculate the next.
            if (dictionary.TryGetValue(ordinalPosition - 1, out previous1))
            {
                dictionary.TryGetValue(ordinalPosition - 2, out previous2); //It's safe to assume if we found n-1, n-2 is there.
                returnValue = previous1 + previous2;
                dictionary.Add(ordinalPosition, returnValue);
                return returnValue;
            }

            //If we've gotten here, there's a gap between the last ordinalPosition and the one requested.
            if (dictionary.Count > 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++)
            {
                dictionary.Add(i, fib.Calculate(i));
            }
            dictionary.TryGetValue(ordinalPosition, out returnValue);
            return returnValue;
        }
    }
}

And the largely unchanged Console program. I only updated the implementation to function, not to take advantage of the caching I added. It's just here to show that my code works. I'm aware of some issues from a previous review.

namespace Challenges
{
    class Program
    {
         static void Main(string[] args)
        {
             Console.WriteLine("How many Fibonacci numbers should I print?");

             int input;
             if (int.TryParse(Console.ReadLine(),out input))
             {
                 WriteOkMesage();
                 WriteLotsOfFibonacci(input);   
             }
             else
             {
                 WriteNotAnIntegerMessage();
             }

            Console.WriteLine(Environment.NewLine + "Let's just pick one at random.");
            Console.WriteLine("What nth number Fibonacci would you like?");

            if (int.TryParse(Console.ReadLine(),out input))
            {
                WriteOkMesage();
                WriteAFibonacci(input);
            }
            else
            {
                WriteNotAnIntegerMessage();
            }

            Console.WriteLine("Press enter to close...");
            Console.ReadLine();
        }

        static private void WriteAFibonacci(int n)
        {
            try
            {
                Fibonacci fib = new Fibonacci();
                Console.WriteLine("The answer is: " + fib.Calculate(n));
            }
            catch(ArgumentOutOfRangeException e)
            {
                WriteErrorMessage(e);
            }
        }

        static private void WriteLotsOfFibonacci(int numberToPrint)
        {
            Fibonacci fib = new Fibonacci();
            try
            {
                for (int i = 1; i <= numberToPrint; i++)
                {
                    Console.WriteLine(fib.Calculate(i));
                }
            }
            catch (ArgumentOutOfRangeException e)
            {
                WriteErrorMessage(e);
            }
        }

        static private void WriteOkMesage()
        {
            Console.WriteLine("Okay!" + Environment.NewLine);
        }

        static private void WriteErrorMessage(Exception e)
        {
            Console.WriteLine(e.Source + " " + e.Message);
        }

        static private void WriteNotAnIntegerMessage()
        {
            Console.WriteLine("That's not an integer! I can't process that.");
        }

    }
}

Answer 1

A Dictionary is the wrong data structure to use for memoization here. An ArrayList A List<int> would be more appropriate. The reason is that the entries are not independent, but rather sequential: it will remember all entries from the 0^th 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.

Answer 2

Basically, you should have code that looks something like this:

while(listOfFibbonaciiValues.Count <= requestedNumber) {
     listOfFibbonaciiValues.Add(listOfFibbonacciValues.lastOne() + listOfFibbonacciValues.secondLastone()); 
}

return listOfFibbonacciiValues[requestedNumber]; 

Answer 3

Two things you could change ordinal position 2 is not a special case but zero and 1 are with that you can change the handling of special cases to this:

if(ordinalPosition < 2) {
    return ordinalPosition;
}

the second thing you can change is after this line:

//If we already have the previous ordinalPosition

you can simply do this:

var res = Calculate(ordinalPosition-2) + Calculate(ordinalPosition-1);
dictionary.Add(ordinalPosition,res);
return res;

If they are in the dictionary they will be returned immediately. If they are not they will be calculated (and stored in the dictionary).

As several have noted you can use a List<int> rather than a Dictionary since they are calculated sequentially but you need to keep the order of the calculations right then

Answer 4

I think you are overcomplicating things. If the number is not in the dictionary, there is no need to check whether \$n-1\$ is in there. Just calculate \$F(n-1) + F(n-2)\$ and let the memoization do its trick.