{"id":25725,"date":"2017-10-25T20:16:31","date_gmt":"2017-10-25T14:46:31","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25725"},"modified":"2017-10-25T20:16:31","modified_gmt":"2017-10-25T14:46:31","slug":"c-programming-fibonacci-numbers","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-fibonacci-numbers\/","title":{"rendered":"C Programming – Fibonacci numbers"},"content":{"rendered":"

The Fibonacci numbers are the numbers in the following integer sequence.<\/p>\n

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \u2026\u2026..<\/p>\n

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation<\/p>\n

Fn = Fn-1 + Fn-2
\nwith seed values<\/p>\n

F0 = 0 and F1 = 1.<\/p>\n

Write a function int fib(int n) that returns Fn. For example, if n = 0, then fib() should return 0. If n = 1, then it should return 1. For n > 1, it should return Fn-1 + Fn-2<\/p>\n

For n = 9
\nOutput:34
\nFollowing are different methods to get the nth Fibonacci number.<\/p>\n[ad type=”banner”]\n

Method 1 ( Use recursion )
\nA simple method that is a direct recursive implementation mathematical recurrence relation given above.<\/p>\n

c program1<\/span> <\/div> 
\/\/Fibonacci Series using Recursion#include<stdio.h>int fib(int n){   if (n <= 1)      return n;   return fib(n-1) + fib(n-2);} int main (){  int n = 9;  printf("%d", fib(n));  getchar();  return 0;}<\/code><\/pre> <\/div>\n
Output<\/p>\n
34<\/pre>\n
Time Complexity:<\/em> T(n) = T(n-1) + T(n-2) which is exponential.<\/p>\n
We can observe that this implementation does a lot of repeated work (see the following recursion tree). So this is a bad implementation for nth Fibonacci number.<\/p>\n
                         fib(5)   \r\n                     \/             \\     \r\n               fib(4)                fib(3)   \r\n             \/      \\                \/     \\\r\n         fib(3)      fib(2)         fib(2)    fib(1)\r\n        \/     \\        \/    \\       \/    \\  \r\n  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)\r\n  \/    \\\r\nfib(1) fib(0)<\/pre>\n
Extra Space:<\/em> O(n) if we consider the function call stack size, otherwise O(1).<\/p>\n[ad type=”banner”]\n
Method 2 ( Use Dynamic Programming )<\/strong>
\nWe can avoid the repeated work done is the method 1 by storing the Fibonacci numbers calculated so far.<\/p>\n
 
 c program2<\/span> <\/div> 
\/\/Fibonacci Series using Dynamic Programming#include<stdio.h> int fib(int n){  \/* Declare an array to store Fibonacci numbers. *\/  int f[n+1];  int 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];} int main (){  int n = 9;  printf("%d", fib(n));  getchar();  return 0;}<\/code><\/pre> <\/div>\n
Output:<\/p>\n
34<\/pre>\n
Time Complexity:<\/em> O(n)
\nExtra Space: <\/em>O(n)<\/p>\n[ad type=”banner”]\n
Method 3 ( Space Optimized Method 2 )<\/strong>
\nWe can optimize the space used in method 2 by storing the previous two numbers only because that is all we need to get the next Fibonacci number in series.<\/p>\n
 
 c program3<\/span> <\/div> 
\/\/ Fibonacci Series using Space Optimized Method#include<stdio.h>int fib(int n){  int a = 0, b = 1, c, i;  if( n == 0)    return a;  for (i = 2; i <= n; i++)  {     c = a + b;     a = b;     b = c;  }  return b;} int main (){  int n = 9;  printf("%d", fib(n));  getchar();  return 0;}<\/code><\/pre> <\/div>\n
Time Complexity: O(n)
\nExtra Space: O(1)<\/p>\n[ad type=”banner”]\nMethod 4<\/strong> ( Using power of the matrix {{1,1},{1,0}} )
\nThis another O(n) which relies on the fact that if we n times multiply the matrix M = {{1,1},{1,0}} to itself (in other words calculate power(M, n )), then we get the (n+1)th Fibonacci number as the element at row and column (0, 0) in the resultant matrix.<\/p>\n
 <\/p>\n
 
 c program4<\/span> <\/div> 
#include <stdio.h> \/* Helper function that multiplies 2 matrices F and M of size 2*2, and  puts the multiplication result back to F[][] *\/void multiply(int F[2][2], int M[2][2]); \/* 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 *\/void power(int F[2][2], int n); int fib(int n){  int F[2][2] = {{1,1},{1,0}};  if (n == 0)      return 0;  power(F, n-1);   return F[0][0];} void multiply(int F[2][2], int M[2][2]){  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];  int 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;} void power(int F[2][2], int n){  int i;  int M[2][2] = {{1,1},{1,0}};   \/\/ n - 1 times multiply the matrix to {{1,0},{0,1}}  for (i = 2; i <= n; i++)      multiply(F, M);} \/* Driver program to test above function *\/int main(){  int n = 9;  printf("%d", fib(n));  getchar();  return 0;}<\/code><\/pre> <\/div>\n
Time Complexity: O(n)
\nExtra Space: O(1)
\nMethod 5 ( Optimized Method 4 )
\nThe method 4 can be optimized to work in O(Logn) time complexity. We can do recursive multiplication to get power(M, n) in the prevous method (Similar to the optimization done in this post)<\/p>\n
 
 C program5<\/span> <\/div> 
#include <stdio.h> void multiply(int F[2][2], int M[2][2]); void power(int F[2][2], int n); \/* function that returns nth Fibonacci number *\/int fib(int n){  int F[2][2] = {{1,1},{1,0}};  if (n == 0)    return 0;  power(F, n-1);  return F[0][0];} \/* Optimized version of power() in method 4 *\/void power(int F[2][2], int n){  if( n == 0 || n == 1)      return;  int M[2][2] = {{1,1},{1,0}};   power(F, n\/2);  multiply(F, F);   if (n%2 != 0)     multiply(F, M);} void multiply(int F[2][2], int M[2][2]){  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];  int 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;} \/* Driver program to test above function *\/int main(){  int n = 9;  printf("%d", fib(9));  getchar();  return 0;}<\/code><\/pre> <\/div>\n
Time Complexity: <\/em>O(Logn)<\/strong>
\nExtra Space:<\/em> O(Logn) if we consider the function call stack size, otherwise O(1).<\/p>\n[ad type=”banner”]\n
Method 6 (O(Log n) Time)<\/strong>
\nBelow is one more interesting recurrence formula that can be used to find n\u2019th Fibonacci Number in O(Log n) time.<\/p>\n
If n is even then k = n\/2:\r\nF(n) = [2*F(k-1) + F(k)]*F(k)\r\n\r\nIf n is odd then k = (n + 1)\/2\r\nF(n) = F(k)*F(k) + F(k-1)*F(k-1)<\/pre>\n
How does this formula work?
\nThe formula can be derived from above matrix equation.
\nfibonaccimatrix<\/p>\n
Taking determinant on both sides, we get
\n(-1)n = Fn+1Fn-1 \u2013 Fn2
\nMoreover, since AnAm = An+m for any square matrix A, the following identities can be derived (they are obtained form two different coefficients of the matrix product)<\/p>\n
FmFn + Fm-1Fn-1 = Fm+n-1<\/p>\n
By putting n = n+1,<\/p>\n
FmFn+1 + Fm-1Fn = Fm+n<\/p>\n
Putting m = n<\/p>\n
F2n-1 = Fn2 + Fn-12<\/p>\n
F2n = (Fn-1 + Fn+1)Fn = (2Fn-1 + Fn)Fn (Source: Wiki)<\/p>\n
To get the formula to be proved, we simply need to do following
\nIf n is even, we can put k = n\/2
\nIf n is odd, we can put k = (n+1)\/2<\/p>\n
Below is C++ implementation of above idea.<\/p>\n
 
 C Program 6<\/span> <\/div> 
\/\/ C++ Program to find n'th fibonacci Number in\/\/ with O(Log n) arithmatic operations#include <bits\/stdc++.h>using namespace std; const int MAX = 1000; \/\/ Create an array for memoizationint f[MAX] = {0}; \/\/ Returns n'th fuibonacci number using table f[]int fib(int n){    \/\/ Base cases    if (n == 0)        return 0;    if (n == 1 || n == 2)        return (f[n] = 1);     \/\/ If fib(n) is already computed    if (f[n])        return f[n];     int k = (n & 1)? (n+1)\/2 : n\/2;     \/\/ Applyting above formula [Note value n&1 is 1    \/\/ if n is odd, else 0.    f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1))           : (2*fib(k-1) + fib(k))*fib(k);     return f[n];} \/* Driver program to test above function *\/int main(){    int n = 9;    printf("%d ", fib(n));    return 0;}<\/code><\/pre> <\/div>\n
Output :<\/p>\n
34<\/pre>\n
Time complexity of this solution is O(Log n) as we divide the problem to half in every recursive call.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
C Programming Fibonacci numbers – Mathematical algorithms – The Fibonacci numbers are the numbers in the following integer sequence. 0, 1, 1, 2, 3, 5, 8, 13<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69866,1,83563,74058],"tags":[74939,71157,74988,75004,69955,74999,74996,75003,74995,71152,75007,74080,70077,72112,72113,70972,74997,75006,75002,74992,74998,75001,74989,75005,74950,74076,74975,74951,74938,74940,74072,74945,72439,74060,72468,74066,70848,74952,74941,74935,74987,74949,75000,74994,74991,74990,74290,74993,74934,74942],"class_list":["post-25725","post","type-post","status-publish","format-standard","hentry","category-c-programming","category-coding","category-fibonacci-numbers","category-mathematical-algorithms","tag-algorithm-of-fibonacci-series","tag-bubble-sort-c-program","tag-c-language-graphics","tag-c-language-online-test","tag-c-language-operator","tag-c-language-questions-and-answers","tag-c-language-structure","tag-c-language-syllabus","tag-c-language-theory","tag-c-program-for-bubble-sort","tag-c-program-for-factorial","tag-c-program-for-fibonacci-series","tag-c-program-for-linear-search","tag-c-program-for-palindrome","tag-c-program-for-prime-number","tag-c-program-for-selection-sort","tag-c-program-sample","tag-c-program-structure","tag-c-programming-pointers","tag-c-programming-question-bank","tag-c-programming-question-paper","tag-c-programming-quiz","tag-c-programming-series-examples","tag-download-c-language","tag-fibonacci","tag-fibonacci-c-program","tag-fibonacci-formula","tag-fibonacci-java","tag-fibonacci-number-program-in-java","tag-fibonacci-program","tag-fibonacci-program-in-c","tag-fibonacci-series","tag-fibonacci-series-algorithm","tag-fibonacci-series-c-program","tag-fibonacci-series-in-c-using-recursion-with-explanation","tag-for-loop-c-programming","tag-for-loop-in-c-programming","tag-how-to-calculate-fibonacci","tag-java-fibonacci","tag-java-program-fibonacci","tag-modular-programming-in-c","tag-number-series-program-in-c","tag-online-c-programming","tag-online-c-programming-test","tag-programs-on-recursion-in-c","tag-recursion-in-c-programming-example","tag-recursion-program-in-c","tag-structure-in-c-programming","tag-write-a-program-to-print-fibonacci-series","tag-write-ac-program-to-generate-fibonacci-series"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25725","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25725"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25725\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25725"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25725"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25725"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}