Calculating Fibonacci sequence in several different ways

Question

I'm doing an experiment trying to freshen up my unit-testing and learn dynamic programming. Every test passes but I'm curious of the result of some of them and worried if I'm doing the testing correctly. Currently I just got the one scenario for each method, with the input of 40, the goal of this test is to test which method is the most efficient for large numbers.

Test result are as follow: 
BottomUp: 7 ms
DynamicFibonacci: 5 sec  
DynamicFibonacci2: 8 ms
MatrixFibonacci: 7 ms
EfficientMatrix: 8 ms
PiVersion: 7 ms
RecursiveFibonacci: 4 sec

I understand the slowness of the recursive, that one makes sense since it does not store the value. The efficientmatrix is however only 1 ms faster and in some test the time even seem to be the same. DynamicFibonacci1 I don't get at all why it's so slow, it should be very similiar to version 2 but the time difference is huge. It's even slower than the recursive one where it does not memoize.

I ran all test individually since I noticed the result differed wildly otherwise, I believe the array value was stored when running them all at once, but that did not seem to be the case when debugging the test individually.

My question is, how can I improve my tests, both method wise and the testing process. It feels like I get slightly different test result just running them once, is there a better way to run several time in a for loop maybe? It just seems like I can't really compare the results this way.

Which method is generally the best to use when using large numbers/heavy calculations like this? I'm originally a mobile Xamarin developer and just trying to learn a bit more on how to speed up some of my other work.

TEST Class // sample method, all of them look the same except calling the different methods.

[TestClass]
public class FibonacciSequenceTest
{
    private const long Number = 40;
    private const long Result = 102334155;

    private readonly FibonacciSequence fibonacciSequence;

    public FibonacciSequenceTest()
    {
       fibonacciSequence = new FibonacciSequence();
    }

    [TestMethod]
    public void MatrixFibonacciCalculatorTest()
    {
        // Act
        var returnValue = fibonacciSequence.MatrixFibonacciCalculator(Number);

        // Assert
        long actual = returnValue;
        Assert.AreEqual(actual, Result);
    }
}

Class and methods

public class FibonacciSequence
{
    private readonly long max = 1000;

    private readonly long[] memoizedFibonacciNumbers;

    public FibonacciSequence()
    {
        memoizedFibonacciNumbers = new[] { max };
    }

    #region MatrixFibonnaciCalculator

    public long MatrixFibonacciCalculator(long n)
    {
        long[,] f = { { 1, 1 }, { 1, 0 } };
        if (n == 0)
            return 0;
        PowerMatrix1(f, n - 1);

        return f[0, 0];
    }

    /* Helper function that multiplies 2  
    matrices F and M of size 2*2, and puts 
    the multiplication result back to F[][] */
    public void MultiplyMatrix1(long[,] F, long[,] M)
    {
        long x = F[0, 0] * M[0, 0] + F[0, 1] * M[1, 0];
        long y = F[0, 0] * M[0, 1] + F[0, 1] * M[1, 1];
        long z = F[1, 0] * M[0, 0] + F[1, 1] * M[1, 0];
        long w = F[1, 0] * M[0, 1] + F[1, 1] * M[1, 1];

        F[0, 0] = x;
        F[0, 1] = y;
        F[1, 0] = z;
        F[1, 1] = w;
    }

    /* Helper function that calculates F[][]  
    raise to the power n and puts the result 
    in F[][] Note that this function is designed 
    only for fib() and won't work as general 
    power function */
    public void PowerMatrix1(long[,] F, long n)
    {
        long i;
        var M = new long[,] { { 1, 1 }, { 1, 0 } };

        // n - 1 times multiply the matrix to 
        // {{1,0},{0,1}} 
        for (i = 2; i <= n; i++)
            MultiplyMatrix1(F, M);
    }

    #endregion

    #region EfficentMatrixFibonacciCalculator

    public long EfficientMatrixFibonacciCalculator(long n)
    {
        var f = new long[,] { { 1, 1 }, { 1, 0 } };
        if (n == 0)
            return 0;
        EfficientPowerMatrix(f, n - 1);

        return f[0, 0];
    }

    public void EfficientPowerMatrix(long[,] F, long n)
    {
        if (n == 0 || n == 1)
            return;
        var M = new long[,] { { 1, 1 }, { 1, 0 } };

        EfficientPowerMatrix(F, n / 2);
        EfficientMultiplyMatrix(F, F);

        if (n % 2 != 0)
            EfficientMultiplyMatrix(F, M);
    }

    public void EfficientMultiplyMatrix(long[,] f, long[,] m)
    {
        long x = f[0, 0] * m[0, 0] + f[0, 1] * m[1, 0];
        long y = f[0, 0] * m[0, 1] + f[0, 1] * m[1, 1];
        long z = f[1, 0] * m[0, 0] + f[1, 1] * m[1, 0];
        long w = f[1, 0] * m[0, 1] + f[1, 1] * m[1, 1];

        f[0, 0] = x;
        f[0, 1] = y;
        f[1, 0] = z;
        f[1, 1] = w;
    }

    #endregion



    public int IterativeFibonacciCalculator(long number)
    {
        int firstNumber = 0, secondNumber = 1, result = 0;

        if (number == 0) return 0; // To return the first Fibonacci number   
        if (number == 1) return 1; // To return the second Fibonacci number   

        for (var i = 2; i <= number; i++)
        {
            result = firstNumber + secondNumber;
            firstNumber = secondNumber;
            secondNumber = result;
        }

        return result;
    }

    public long RecursiveFibonacciCalculator(long number)
    {
        if (number <= 1)
        {
            return number;
        }

        return RecursiveFibonacciCalculator(number - 1) + RecursiveFibonacciCalculator(number - 2);
    }

    public long DynamicFibonacciCalculator(long number)
    {
        long result;
        var memoArrays = new long[number + 1];
        if (memoArrays[number] != 0) return memoArrays[number];
        if (number == 1 || number == 2)
        {
            result = 1;
        }
        else
        {
            result = DynamicFibonacciCalculator(number - 1) + DynamicFibonacciCalculator(number - 2);
            memoArrays[number] = result;
        }

        return result;
    }

    public long DynamicFibonacciCalculator2(long n)
    {
        // Declare an array to  
        // store Fibonacci numbers. 
        // 1 extra to handle  
        // case, n = 0 
        var f = new long[n + 2];
        long i;

        /* 0th and 1st number of the  
           series are 0 and 1 */
        f[0] = 0;
        f[1] = 1;

        for (i = 2; i <= n; i++)
            /* Add the previous 2 numbers 
                                   in the series and store it */
            f[i] = f[i - 1] + f[i - 2];

        return f[n];
    }

    // Helper method for PiCalculator
    public long PiFibonacciCalculator(long n)
    {
        double phi = (1 + Math.Sqrt(5)) / 2;
        return (long)Math.Round(Math.Pow(phi, n) / Math.Sqrt(5));
    }



    public long BottomUpFibonacciCalculator(long n)
    {
        long a = 0, b = 1;

        // To return the first Fibonacci number  
        if (n == 0) return a;

        for (long i = 2; i <= n; i++)
        {
            long c = a + b;
            a = b;
            b = c;
        }

        return b;
    }
}

Answer 1

DynamicFibonacciCalculator is slow because you create a new memoArrays for each recursion, so it will never contain any precalculated values, and it behave just as the normal recursive version (and even worse because of the overhead of allocating the arrays.

public long DynamicFibonacciCalculator(long number)
{
    long result;
    var memoArrays = new long[number + 1];
      ...

You should maintain the memoArrays outside of the recursion method. You could maybe do the recursion in an local function:

public static long DynamicFibonacciCalculator(long number)
{
  if (num <= 1)
  {
    return num;
  }

  long[] memoArrays = new long[number + 1];

  long Recursion(long num)
  {
    if (num <= 1)
    {
      return num;
    }

    long result;

    if (memoArrays[num] != 0)
    {
      return memoArrays[num];
      ....

  }

  return Recursion(number);
}

---

All your methods don't depend on instance members, so it would be more correct to make them static (and the helpers could be static as well):

  public static class FibonacciSequence
  {
    #region MatrixFibonnaciCalculator

    public static long MatrixFibonacciCalculator(long n)
    {
      long[,] f = { { 1, 1 }, { 1, 0 } };
      if (n == 0)
        return 0;
        ...

---

You could optimize the test class by making a common test method that takes a delegate as argument:

public class FibonacciSequenceTest
{
  private const long Number = 40;
  private const long Result = 102334155;

  public FibonacciSequenceTest()
  {
  }

  public void FibonacciTester(Func<long, long> method, string methodName)
  {
    // Act
    var returnValue = method(Number);

    // Assert
    long actual = returnValue;
    Assert.AreEqual(actual, Result, $"{methodName} produced wrong result.");
  }

  [TestMethod]
  public void TestBottomUpFibonacciCalculator()
  {
    FibonacciTester(FibonacciSequence.BottomUpFibonacciCalculator, nameof(FibonacciSequence.BottomUpFibonacciCalculator));
  }

  // TODO: Test methods for each Fib method...


}

In this way it is easier to maintain, and you avoid repeating yourself.

Answer 2

Currently I just got the one scenario for each method, with the input of 40, the goal of this test is to test which method is the most efficient for large numbers.

Running one iteration of a test case is not resilient to external interference. What if your CPU is doing other stuff at the same time. To get better comparison results, you should benchmark tests.

Jon Skeet's Micro-benchmark Framework might be an option, or you could roll out your own benchmark tests.

A trivial example of a benchmark test to get an idea:

  [TestMethod]
  public void TestBottomUpFibonacciCalculator()
  {
      for (int i = 0; i < 10000; i++)
      {
          FibonacciTester(FibonacciSequence.BottomUpFibonacciCalculator,
              nameof(FibonacciSequence.BottomUpFibonacciCalculator));
      }
  }