Fibonacci numbers (sketch in C #)

    Probably many students had to study recursion using the example of calculating Fibonacci numbers. The task is certainly an academic one, and it illustrates recursion clearly worse than calculating, say, factorials, but it is interesting in that it has many solutions of varying degrees of perversion. In this post - a small sketch on this topic.


    I think that nobody will be surprised by the “default” solution for calculating the Nth Fibonacci number:

    static int fib(int n)
    {
      return n > 1 ? fib(n - 1) + fib(n - 2) : n;
    }
    

    Also, there is a rather “fashionable” form of writing this solution that uses the Y-combinator:

    Func fib  = Y(f => n => n > 1 ? f(n - 1) + f(n - 2) : n);
    

    Where is Ydefined, for example, like this:

    static Func Y(Func, Func> f)
    {
      Func g = null;
      g = f(a=>g(a));
      return g;
    }
    

    For large N, this approach is unproductive. How to count the number N faster? To begin with, let's remember why, for example, x*xit is considered faster than Math.Pow(x,2)? Because for an integer degree, you can not only do without Taylor series, but also optimize the calculation for large degrees by creating temporary variables. For example, x 4 can be thought of as int y = x * x; return y * y;- and the greater the degree, the greater the savings.

    Why am I? In addition, the Fibonacci number can be calculated using the following formula:




    Now it is clear why do we need integer exponentiation? For matrices, you can do the same, only first you need to understand how this is generally done. On the Internet, I found perhaps the perfect algorithmwhich optimizes integer exponentiation. Please note that in the example below, the degree is of type short.

    public static long IntPower(int x, short power)
    {
      if (power == 0) return 1;
      if (power == 1) return x;
      int n = 15;
      while ((power <<= 1) >= 0) n--;
      long tmp = x;
      while (--n > 0)
        tmp = tmp * tmp *
             (((power <<= 1) < 0) ? x : 1);
      return tmp;
    }
    

    Now it remains only to determine the 2 × 2 matrix. Here one could use some kind of library, but I decided to write the simplest possible structure:

    struct mtx2x2
    {
      public int _11, _12, _21, _22;
      public static mtx2x2 operator*(mtx2x2 lhs, mtx2x2 rhs)
      {
        return new mtx2x2
                 {
                   _11 = lhs._11*rhs._11 + lhs._12*rhs._21,
                   _12 = lhs._11*rhs._12 + lhs._12*rhs._22,
                   _21 = lhs._21*rhs._11 + lhs._22*rhs._21,
                   _22 = lhs._21*rhs._12 + lhs._22*rhs._22
                 };
      }
    }
    

    After that, it was necessary to determine two constants that are useful to us - the matrix that we will raise to the power and the identity matrix:

    private static readonly mtx2x2 fibMtx = new mtx2x2 {_11 = 1, _12 = 1, _21 = 1};
    private static readonly mtx2x2 identity = new mtx2x2 {_11 = 1, _22 = 1};
    

    Now we can rewrite the method IntPower()for 2 × 2 matrices:

    public static mtx2x2 IntPower(mtx2x2 x, short power)
    {
      if (power == 0) return identity;
      if (power == 1) return x;
      int n = 15;
      while ((power <<= 1) >= 0) n--;
      mtx2x2 tmp = x;
      while (--n > 0)
        tmp = (tmp * tmp) * (((power <<= 1) < 0) ? x : identity);
      return tmp;
    }
    

    And define a new method for calculating the Fibonacci number:

    static int fibm(short n)
    {
      return IntPower(fibMtx, (short)(n-1))._11;
    }
    

    That's all. I think that it makes no sense to compare performance - I fib(40)count 4 seconds, and it fibm(40)is displayed instantly. ■

    Also popular now: