Several methods for implementing Fibonacci sequences in C#

What is a Fibonacci sequence? One of the classic mathematical problems; the Fibonacci sequence, also known as the golden segmentation sequence, refers to a sequence: 1, 1, 2, 3, 5, 8, 13, 21,... I believe that when you see this sequence, you can easily calculate the values of the following several terms. So what are the rules? Simply put, the sum of the first two terms is the value of the third term, and the recursive algorithm is used to calculate the 50th position.

This sequence starts from the third term, and each term is equal to the sum of the first two terms.

Fibonacci sequence: {1,1,2,3,5,8,13,21...}

Recursive algorithm, the longest-consuming algorithm, is very inefficient.

public static long CalcA(int n)
{
  if (n <= 0) return 0;
  if (n <= 2) return 1;
  return checked(CalcA(n - 2) + CalcA(n - 1));
}

Implemented by loop

public static long CalcB(int n)
{
  if (n <= 0) return 0;
  var a = 1L;
  var b = 1L;
  var result = 1L;
  for (var i = 3; i <= n; i++)
  {
    result = checked(a + b);
    a = b;
    b = result;
  }
  return result;
}

Improved writing through loop

public static long CalcC(int n)
{
  if (n <= 0) return 0;
  var a = 1L;
  var b = 1L;
  for (var i = 3; i <= n; i++)
  {
    b = checked(a + b);
    a = b - a;
  }
  return b;
}

General formula method

/// &lt;summary&gt;
/// F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}
/// &lt;/summary&gt;
/// &lt;param name="n"&gt;&lt;/param&gt;
/// &lt;returns&gt;&lt;/returns&gt;
public static long CalcD(int n)
{
  if (n &lt;= 0) return 0;
  if (n &lt;= 2) return 1; // Add it to reduce the calculation.  var a = 1 / (5);
  var b = ((1 + (5)) / 2, n);
  var c = ((1 - (5)) / 2, n);
  return checked((long)(a * (b - c)));
}

Other methods

using System;
using ;


namespace Fibonacci
{
  class Program
  {
    static void Main(string[] args)
    {
      ulong result;

      int number = 10;
      ("************* number={0} *************", number);

      Stopwatch watch1 = new Stopwatch();
      ();
      result = F1(number);
      ();
      ("F1({0})=" + result + " time consuming：" + , number);

      Stopwatch watch2 = new Stopwatch();
      ();
      result = F2(number);
      ();
      ("F2({0})=" + result + " time consuming：" + , number);

      Stopwatch watch3 = new Stopwatch();
      ();
      result = F3(number);
      ();
      ("F3({0})=" + result + " time consuming：" + , number);

      Stopwatch watch4 = new Stopwatch();
      ();
      double result4 = F4(number);
      ();
      ("F4({0})=" + result4 + " time consuming：" + , number);

      ();

      ("Finish");
      ();
    }

    /// &lt;summary&gt;
    /// Iteration method    /// &lt;/summary&gt;
    /// &lt;param name="number"&gt;&lt;/param&gt;
    /// &lt;returns&gt;&lt;/returns&gt;
    private static ulong F1(int number)
    {
      if (number == 1 || number == 2)
      {
        return 1;
      }
      else
      {
        return F1(number - 1) + F1(number - 2);
      }
      
    }

    /// &lt;summary&gt;
    /// Direct method    /// &lt;/summary&gt;
    /// &lt;param name="number"&gt;&lt;/param&gt;
    /// &lt;returns&gt;&lt;/returns&gt;
    private static ulong F2(int number)
    {
      ulong a = 1, b = 1;
      if (number == 1 || number == 2)
      {
        return 1;
      }
      else
      {
        for (int i = 3; i &lt;= number; i++)
        {
          ulong c = a + b;
          b = a;
          a = c;
        }
        return a;
      }
    }

    /// &lt;summary&gt;
    /// Matrix method    /// &lt;/summary&gt;
    /// &lt;param name="n"&gt;&lt;/param&gt;
    /// &lt;returns&gt;&lt;/returns&gt;
    static ulong F3(int n)
    {
      ulong[,] a = new ulong[2, 2] { { 1, 1 }, { 1, 0 } };
      ulong[,] b = MatirxPower(a, n);
      return b[1, 0];
    }

    #region F3
    static ulong[,] MatirxPower(ulong[,] a, int n)
    {
      if (n == 1) { return a; }
      else if (n == 2) { return MatirxMultiplication(a, a); }
      else if (n % 2 == 0)
      {
        ulong[,] temp = MatirxPower(a, n / 2);
        return MatirxMultiplication(temp, temp);
      }
      else
      {
        ulong[,] temp = MatirxPower(a, n / 2);
        return MatirxMultiplication(MatirxMultiplication(temp, temp), a);
      }
    }

    static ulong[,] MatirxMultiplication(ulong[,] a, ulong[,] b)
    {
      ulong[,] c = new ulong[2, 2];
      for (int i = 0; i &lt; 2; i++)
      {
        for (int j = 0; j &lt; 2; j++)
        {
          for (int k = 0; k &lt; 2; k++)
          {
            c[i, j] += a[i, k] * b[k, j];
          }
        }
      }
      return c;
    }
    #endregion

    /// &lt;summary&gt;
    /// General formula method    /// &lt;/summary&gt;
    /// &lt;param name="n"&gt;&lt;/param&gt;
    /// &lt;returns&gt;&lt;/returns&gt;
    static double F4(int n)
    {
      double sqrt5 = (5);
      return (1/sqrt5*(((1+sqrt5)/2,n)-((1-sqrt5)/2,n)));
    }
  }
}

OK, that's all. The long type used to store the result, and when n>92, the memory will overflow.

The above is all the content of this article. I hope it will be helpful to everyone's study and I hope everyone will support me more.