# 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.

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)
{
return 0;
}

if (ordinalPosition == 1 || ordinalPosition == 2)
{
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;
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;
}
return returnValue;
}

//If all else fails, start at the beginning.
Fibonacci fib = new Fibonacci();
for (int i = 0; i <= ordinalPosition; 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;
{
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?");

{
WriteOkMesage();
WriteAFibonacci(input);
}
else
{
WriteNotAnIntegerMessage();
}

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

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.");
}

}
}


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 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.

• Why a static constructor? What's the benefit vs. the way I currently declare the constructor? Thanks for pointing me to ArrayList. – RubberDuck Jul 13 '14 at 12:33
• Don't use ArrayList, that's the old pre-generic version. Instead use List<T>. – svick Jul 13 '14 at 13:49
• I've put together some code based on your excellent suggestions. It's available here, but unfortunately ideone doesn't support System.Numerics. – mjolka Jul 14 '14 at 3:39
• @mjolka Fibs should have a lowercase, right? – 200_success Jul 14 '14 at 3:43
• D'oh, yes. I'll update it. Feel free to add the code to your answer if you like it. – mjolka Jul 14 '14 at 3:44

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

while(listOfFibbonaciiValues.Count <= requestedNumber) {
}

return listOfFibbonacciiValues[requestedNumber];

• That's a rather naïve and simplistic implementation. You're ruining the memoization. – ANeves Jul 14 '14 at 17:08
• @ANeves you misunderstand me. You keep the list between calls to the function. – Winston Ewert Jul 14 '14 at 17:11
• Sorry, that is true. – ANeves Jul 14 '14 at 17:21

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);
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

• @ckuhn203 *memoization (no r) – ANeves Jul 14 '14 at 17:10
• Good call out. I realized that F(2) isn't a special case while I was working on this the other night. – RubberDuck Jul 17 '14 at 12:58

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.

• But what happens if Fn-1 isn't in the dictionary? It's entirely possible to call fib.Calculate(2); and then call fib.Calculate(9);. – RubberDuck Jul 13 '14 at 12:36
• I think you're onto something, but I could use some clarification. – RubberDuck Jul 13 '14 at 16:27
• This would simplify the code, but it would mean that you will use recursion which is probably less efficient than iteration. – Winston Ewert Jul 13 '14 at 16:51
• Recursion looks very nice for Fibonacci, but unfortunately I think you run out of stack frames too quickly. – Ben Aaronson Jul 14 '14 at 19:12
• @ckuhn203 It should be fast if you cache the results for each number. Alternatively the naive recursive approach can be improved on by F(n, prev, curr) = F(n-1, curr, prev + curr) for n > 0 and = curr for n <= 2. Then Fib(n) = F(n, 1, 1). Still hit stack overflow issues though – Ben Aaronson Jul 15 '14 at 8:37