In the current article I have decided to show three ways of calculating the Fibonacci numbers in C#. The reason for this is, because Fibonacci is usually given as an example for recursion and it is probably the worst way to calculate it. Thus, let’s start with the three ways to calculate it.
- Fibonacci with recursion
The way to calculate the n-th Fibonacci with recursion is pretty straight forward – in order to calculate each number, you should calculate the numbers before and etc, until you get the bottom of the recursion. Then you should make as many recursion calls as needed. Pretty much, to calculate the 35th Fibonacci number, you should be doing above 29 Million calculations. Which has taken my i7 PC about half second. Thus, this is really not the best way!
- Fibonacci with memoization
Here you do recursion, but you remember the value of each Fibonacci. Thus, instead of 29 Million for 35th Fibonacci you do 37 calculations. And it takes just 0.002 seconds.
- The fastest Fibonacci
This is actually how everything starts. If you have never heard about recursion and you wanted to calculate Fibonacci, you would simply make a for-loop for it. And swap the values. My PC has carried it out within really quick time, it could not even write it down 🙂
These are the results:
The first two options – with and without memoization are done through one function, where I have an optional boolean parameter “with_memo” for it. Here comes the code of the Fibonacci:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
using System; class FibonacciChecks { public static long[] my_memo; public static DateTime my_time; public static long my_counter; static void Main() { Console.WriteLine("Enter number between 2 and 1300 for Fibonacci calculation:"); long k = long.Parse(Console.ReadLine()); my_memo = new long[k+1]; my_counter = 0; my_time = DateTime.Now; Console.WriteLine("\n{0}", FibWithMemo(k)); Console.WriteLine("Calculations {0}", my_counter); Console.WriteLine(DateTime.Now - my_time); my_counter = 0; my_time = DateTime.Now; Console.WriteLine("\n{0}",FibWithMemo(k, false)); Console.WriteLine("Calculations {0}", my_counter); Console.WriteLine(DateTime.Now - my_time); my_counter = 2; //Here we already have the first two numbers, so it is a bit unfair my_time = DateTime.Now; Console.WriteLine("\n{0}", FibWithLoop(k)); Console.WriteLine("Calculations {0}", my_counter); Console.WriteLine(DateTime.Now - my_time); } static long FibWithLoop(long counter_inside) { long f1 = 1; long f2 = 1; long f_result = 0; for (my_counter=2; my_counter < counter_inside; my_counter++) { f_result = f1 + f2; f1 = f2; f2 = f_result; } return f_result; } static long FibWithMemo(long counter_inside, bool with_memo = true) { if (with_memo) { if (my_memo[counter_inside] != 0) return my_memo[counter_inside]; } my_counter++; if (counter_inside == 0) return 0; if (counter_inside == 1) return 1; my_memo[counter_inside] = FibWithMemo(counter_inside - 1, with_memo) + FibWithMemo(counter_inside - 2, with_memo); return my_memo[counter_inside]; } } |
Available also in GitHub here.
Enjoy it!