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