# Calculating Fibonacci sequence in several different ways

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;

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;

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

• F(40) isn't exactly a large number. Here's an efficient algorithm in Java which calculates F(10000000) in less than 2 seconds on my laptop. And here's more info about the algorithm. Jul 23 '19 at 10:15
• I guess, the goal however was just to test out dynamic programming a bit and see how it compares to a iterative function. What I learned is, dynamic programming is definently useful but MAN for loops are pretty darn fast Jul 24 '19 at 11:12

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.

• This is the whole functional vs interface approach dilemma. You would opt for static classes and executing them with Func. I would favor an interface and instances rather than static classes. Jul 22 '19 at 15:10
• @dfhwze: Normally I agree in that, but I regard the Fibonacci method just as another Math function for which it would be tedious if you would have to instantiate a Math object each time you need one of its methods (Sqrt(), Pow(), etc.) - You could of course have a global Math instance hanging around, but that is "ugly" IMO.
– user73941
Jul 22 '19 at 15:18
• I would also agree the chosen algorithm should end up as Math.Fibonacci or something like that. For the sake of comparing several methods, I would use an interface (for this trivial domain). So yes, in production code, I agree with the static function in a Math library. Jul 22 '19 at 15:21
• Hey @HenrikHansen, great answer! Especially with the delegate, combining that one with the benchmark should really improve my tests! The one thing i'm unsure about is the static one, I honestly don't understand when it's best to use static and when it's best to use instances. Could you explain further why static or maybe you got a good link to read regarding this? Thanks! Jul 22 '19 at 16:53
• @JsonDork: If a method or function has no side effects and its result is only dependent on its argument (produce the same result for the same arguments when called more than once), it may be candidate as a static method - in functional programming it's called a pure function.
– user73941
Jul 22 '19 at 18:12

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

• Woah! Thanks! This one is really good, didn't know about benchmark but will try to change it to one instead/read up on it a bit more. But this really helps me, because manually running tests always seemed like a unreliable way of doing them. Great answer! Jul 22 '19 at 16:50