Generating Fibonacci Numbers

A person from the thirteenth century, named Leonardo Pisano, known as Fibonacci depicted the following problem in his book Liber abaci: In an island two rabbits are placed. Two rabbits can reproduce after they are two months old. First two months there are one pair of rabbits, they reproduce after 2 months and produce another pair. The new born pair does not reproduce until they are 2 months old, the older pair produces another pair on the 4^th month. Reproducing like this how many pairs of rabbits would be there in the island after n months, under the condition no rabbits die. The Fibonacci series is where each represents the number of rabbit pairs in the island on month n.

In this post we will see the obvious recursive solution, an iterative solution and a solution with which you can find the n^th fibonacci number directly from an equation.

Fibonacci Series

The Fibonacci numbers are shown belows:

From the origin of the Fibonacci numbers and also studying the series it is clear that each number of the series is generated from the addition of the previous two numbers. Initially the first two number of the series are 1 , and that is given. That is the first two months there are 1 pair of rabbit in the island.

Recursive Solition

It is easy to make a recursive algorithm, because each element can be found from the previous two element. To make the recursive algorithm the base condition will be

and the recursive relation is

where

where n belongs to positive numbers greater than 1.
Note that the Fibonacci series starts from 1, that is the first number of the series is 1, which represents

The above recursive definition is as follows:

/* Topic: Program generate the 'n'th Fibonacci number
 * Source: https://phoxis.wordpress.com
 */

#include<stdio.h>

long double fibo (long double n);

int
main (void)
{
  int n;
  long double f;

  printf ("Generate n th Fibonacci Number.\n");
  printf ("Enter \"n\": ");
  scanf ("%d", &n);

  if (n <= 0)
  {
    printf ("\nEnter a positive number");
    return 0;
  }

  f = fibo (n);

  printf ("\nFibonacci[%d] = %LE = %.0LF\n", n, f, f);
  return 0;
}

long double
fibo (long double n)
{
  if (n <= 1)
    return n;
  return (fibo (n - 2) + fibo (n - 1));
}

Recursion is easy but it has got its own limitations. First in this case this is very time consuming for somewhat larger input. Enter 50 to get the 50th Fibonacci number and it would take a long time. Second, the system stack is used for the recursive calls. The system stack is limited, so for greately huge input the system stack would be full and the program will crash. Although filling the system stack is difficult in generel, if a code is not purposely done to do so.

Iterative Solution

We can think of an iterative method to overcome these limitations. Also the iterative method is simple. We take three variables f, f1 and f2 . f1 and f2 are initilized to 1, as the first condition. So the first two elements of the Fibonacci series are there. To get the 3^rd Fibonacci number we do f=f1+f2. After this step the we update f1 and f2 : the new value of f1 is f2, and the new value of f2 is f. The idea is depicted below.

f1  f2  f
1   1   2

   f1  f2  f
1   1   2  3

       f1  f2   f
1   1   2   3   5

           f1  f2   f
1   1   2   3   5   8

To generate the n^th Fibonacci number we iterate n-2 times (the first two integers are initilized). We present the iterative code to get the n^th Fibonacci number.

/* Topic: Program generate the 'n'th Fibonacci number
 * Source: https://phoxis.wordpress.com
 */

#include <stdio.h>

int
main (void)
{
  long double f1 = 1, f2 = 0, f;
  int n, i;

  printf ("Generate n th Fibonacci Number.\n");
  printf ("Enter \"n\": ");
  scanf ("%d", &n);

  if (n <= 0)
  {
    printf ("\nEnter a positive number");
    return 0;
  }

  for (i = 0; i < n; i++)
    {
      f = f1 + f2;
      /* Print 'f' here to print the series */
      f1 = f2;
      f2 = f;
    }
  /* Print number with exponent representation and then plain number */
  printf ("\nFibonacci[%d] = %LE = %.0LF\n", n, f, f);
  return 0;
}

A Better Iterative Solution

Can we make some more optimizations to the above iterative method? Yes we can. The above example iterates n-2 times and generates n-2 Fibonacci numbers, one in each iteration. We can optimize such that it generates two fibonacci numbers in each iteration, so it iterates (n-2)/2 times. We take two variables f1 and f2. f1 is initilized with 0, and f2 with 1. The operations in each iterations are as below

/* f1 contains k th Fibonacci number */
/* f2 contains k+1 th Fibonacci number */

f1=f1+f2;
/* now f1 contains k+2 th Fibonacci number

f2=f1+f2;
/* now f2 contains k+3 the Fibonacci number */

if f1 and f2 contains k^th and (k+1)^th Fibonacci numbers , then after tha above operations they will contain (k+2)^th and (k+3)^th Fibonacci numbers. This is because, after f1=f1+f2 the value of f1 is updated to (k+2)^th Fibonacci number. Now the operation f2=f1+f2 adds the (k+1)^th and the (k+2)^th Fibonacci numbers and get the (k+3)^th Fibonacci numbers. This is depicted below. Note that because Fibonacci sequence starts from 1, f2 always contain odd Fibonacci numbers, and f1 Even fibonacci numbers.

f1  f2
0   1 

      f1  f2
0  1   1   2

              f1   f2
0  1   1   2   3   5

                      f1   f2
0  1   1   2   3   5   8   13

                               f1  f2
0  1   1   2   3   5   8   13  21  34

To code for this algorithm is presented below.

/* Topic: Program generate the 'n'th Fibonacci number
 * Source: https://phoxis.wordpress.com
 */

#include <stdio.h>

int
main (void)
{
  long double f1 = 0, f2 = 1;
  int i, n;

  printf ("Generate n th Fibonacci Number.\n");
  printf ("Enter \"n\": ");
  scanf ("%d", &n);

  if (n <= 0)
  {
    printf ("\nEnter a positive number");
    return 0;
  }

  for (i = 0; i < n / 2; i++)
    {
      /* print 'f1' and 'f2' here to print series */
      f1 = f1 + f2;
      f2 = f1 + f2;
    }

  /* Even */
  if (n % 2 == 0)
    printf ("\nFibonacci[%d] = %LE = %.0LF\n", n, f1, f1);
  /* Odd */
  else
    printf ("\nFibonacci[%d] = %LE = %.0LF\n", n, f2, f2);

  return 0;
}

Note in this algorithm only the first number of the series is initilized, another is kept 0. So to negerate the nth number the loop will iterate (n-1) times. Also because it generates two Fibonacci numbers in each iteration it always generates even number of primes. Because f2 is initilized to the 1^st Fibonacci number of the series, it will always contain odd fibonacci numbers (as 1 is odd), and from after the first iteration f1 will contain even Fibonacci numbers. To generate n^th Fibonacci number where n is even, the loop will iterate (n/2) times generating n<supth Fibonacci number in f1, and when n is odd then the loop will also iterate (n/2) times generating (n+1)^th Fibonacci number in f2, so we get the n^th Fibonacci number in f1. The last if-else condition prints the correct output according to if n is even or odd.

Yet another iterative solution is possible which generates one Fibonacci numbers in each iteration, but uses two variables instead of three. I am also presenting the loop snippet below.

for (i = 0; i < n; i++)
  {
    b = a + b;
    a = b - a;
  }

After all these we come to yet another solution. This one is derived from the recursive definition. The recurrence relation is

This is a linear homogeneous equation with constant coefficients with two distinct roots. Solving this equation we get the following relation.

With this we can instantly get the n^th Fibonacci number without any iterations.
The equation is translated into C Language syntax

r5 = sqrt(5);
f = (powl((1+r5)/2,n)/r5) - (powl((1-r5)/2,n)/r5);

The implementation is below:

/* Topic: Program generate the 'n'th Fibonacci number
 * Source: https://phoxis.wordpress.com
 */

/* NOTE: Error starts at input 85, because of approximation of
 * high powers
 */

#include <stdio.h>
#include <math.h>

int
main (void)
{
  int n;
  long double f, r5 = sqrtl (5), t1, t2;

  printf ("Generate n th Fibonacci Number.\n");
  printf ("Enter \"n\": ");
  scanf ("%d", &n);

  if (n <= 0)
  {
    printf ("\nEnter a positive number");
    return 0;
  }

  f = (powl ((1 + r5) / 2, n) / r5) - (powl ((1 - r5) / 2, n) / r5);

  printf ("\nFibonacci[%d] = %LE = %.0LF\n", n, f, f);
  return 0;
}

Although there is no explicit iteration, but when programming the powl() would calculate the power iterating. So there is an implicit iteration in this technique. The powl() function is a varient of the pow() function. pow() takes and returns double. The powl() takes and returns long double. Because the datatypes are declared as long double , powl() is used.
This method can calculate faster than the above iterative method.

There is a problem with this method. In a computer the fractions are stored in limited memory so approximations occur. Because this method has square root and divisions such errors occur. For small input the program acts fine as the amount of error cannot be represented by computer memory. With the increase of input the equation’s powers gets high and the error gets amplified. For the above code the error starts at input 91 in my system. The 91th Fibonacci number is 4660046610375530309, but it outputs 4660046610375530310
instead.

Note: This includes the math.h library. When compiling with gcc use the -lm switch to link the glibc math library.

gcc fibonacci.c -lm -o fibo