12
\$\begingroup\$

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

    }
}
\$\endgroup\$
7
\$\begingroup\$

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.

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

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

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

return listOfFibbonacciiValues[requestedNumber]; 
\$\endgroup\$
3
  • \$\begingroup\$ That's a rather naïve and simplistic implementation. You're ruining the memoization. \$\endgroup\$
    – ANeves
    Jul 14 '14 at 17:08
  • \$\begingroup\$ @ANeves you misunderstand me. You keep the list between calls to the function. \$\endgroup\$ Jul 14 '14 at 17:11
  • \$\begingroup\$ Sorry, that is true. \$\endgroup\$
    – ANeves
    Jul 14 '14 at 17:21
2
\$\begingroup\$

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

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

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.

\$\endgroup\$
11
  • \$\begingroup\$ 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);. \$\endgroup\$
    – RubberDuck
    Jul 13 '14 at 12:36
  • \$\begingroup\$ I think you're onto something, but I could use some clarification. \$\endgroup\$
    – RubberDuck
    Jul 13 '14 at 16:27
  • 1
    \$\begingroup\$ This would simplify the code, but it would mean that you will use recursion which is probably less efficient than iteration. \$\endgroup\$ Jul 13 '14 at 16:51
  • \$\begingroup\$ Recursion looks very nice for Fibonacci, but unfortunately I think you run out of stack frames too quickly. \$\endgroup\$ Jul 14 '14 at 19:12
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ Jul 15 '14 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.