Program to Calculate nth Fibonacci Number in C Language
Program Description:
Write a Program to Calculate the nth Fibonacci Number in C Programming Language. The program should accept a number from the user and calculate the nth Fibonacci Number in the Fibonacci Series.
Fibonacci Series:
The Fibonacci series is a series of whole numbers in which each number is the sum of the two preceding numbers. Beginning with and 1, the sequence of Fibonacci numbers would be 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, etc.
The formula to calculate Fibonacci Series is n = (n-1) + (n-2).
where (n-1) means “the last number before n in the series” and (n-2) refers to “the second last one before n in the series.”
F{n} = F{n-1} + F{n-2} so F{0} = 0 and F{1} = 1, etc.
So the zeroth Fibonacci number is . And First Fibonacci Number is 1, etc.
Here is the table which shows the first 11 Fibonacci numbers in Fibonacci Series.
| n | nth Fibonacci Number |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
| 7 | 13 |
| 8 | 21 |
| 9 | 34 |
| 10 | 55 |
So if you the user want the 9th Fibonacci number, Then Program should display the value as 34. And The program also should display the error message if the user enters Invalid input.
📢 Zeroth Fibonacci Number is Zero (0) and First Fibonacci Number is 1
Excepted Inputs and Outputs:
Input:
Enter which fibonacci number(nth) you want to print : 10
Output:
10(th) Fibonacci Number in Fibonacci series is : 55
Pre-Requisites:
- While Loop in C Language
- For Loop in C Language with Example Programs
- do while loop in Language with example programs
- Goto Statement
Program to Calculate nth Fibonacci Number in C Algorithm:
- Take the Input from the User and store it in variable num
- Check if the num is valid Input, We won’t allow the Negative numbers. If the user enters a negative number, then display an error message ( Invalid Input, Please provide valid number ) and stop the program.
- Initialize the first two Fibonacci numbers i.e zero(0) and One(1). We are using the variables i and j respectively.
- We calculate the next Fibonacci number based on the previous two Fibonacci numbers as specified in the formula – F{n} = F{n-1} + F{n-2}
- So Calculate the next Fibonacci number k using the previous two numbers i and j
- Check if the num is equal zero (0) or One(1), if so, Then display the result based on num and stop the program.
- If num is greater than the 1, Then we need to find the nth ( numth) Fibonacci number. To do that we use the Loop.
- Start from the
1 ( we use
cnt variable
cnt = 1) and go up to the
num-1. At Each iteration
- Move forward by assigning the j value to i ( i = j), k value to j ( j = k)
- Finally, create the next Fibonacci number in the Fibonacci series by adding the previous two numbers i and j ( k = i + j)
- Increment the counter i.e cnt++
- This loop will continue until the Loop condition cnt < num-1 becomes False
- Once the above loop terminated, Then we got our Nth Fibonacci Number in Fibonacci Series. Print the results onto the console using the printf statement.
Let’s translate the above pseudo-code into the C code.
Calculate nth Fibonacci Number in C Language Program:
|
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 |
/* C program to calculate nth Fibonacci Number using for loop */ #include<stdio.h> int main() { int i,j,k,num,cnt; printf("Enter which fibonacci number(nth) you want to print : "); scanf("%d",&num); // check 'num', display error on Invalid input. // Our Fibonacci numbers starts from '0', So don't allow negative numbers. if(num < 0) { printf("Invalid Input, Please provide valid number \n"); return 0; } /* * First two numbers in Fibonacci Series is 0 and 1 * so We are using the variables 'i' and 'j' as the * first two numbers in Fibonacci Series */ i=0; j=1; k=i+j; // Check if if(num==0) { printf("0th Fibonacci Number in Fibonacci Series is : %d\n",i); return 0; } if(num==1) { printf("1st Fibonacci Number in Fibonacci Series is : %d\n",j); return 0; } /* * 'cnt' is 1 because we already have i and j as first two numbers i.e 0th and 1st numbers * So our 'cnt' is starting from '0', goes uptp 'num-1' */ cnt=1; for(cnt; cnt<num-1; cnt++) { i=j; j=k; // calculate next fibonacci number by adding new 'i' and 'j' k=i+j; } printf("%d(th) Fibonacci Number in Fibonacci series is : %d\n",num,k); return 0; } |
Program Output:
Compile and run the program using your favorite IDE. We are using the GCC Compiler.
Compile the program.
$ gcc nth-fib.c
The above command generates the executable named a.out. Run it.
|
1 2 3 4 |
$ ./a.out Enter which fibonacci number(nth) you want to print : 10 10(th) Fibonacci Number in Fibonacci series is : 55 $ |
As you can see the program is giving the expected output. Let’s try a few more tests
|
1 2 3 4 5 6 7 8 9 10 |
$ ./a.out Enter which fibonacci number(nth) you want to print : 7 7(th) Fibonacci Number in Fibonacci series is : 13 $ ./a.out Enter which fibonacci number(nth) you want to print : 20 20(th) Fibonacci Number in Fibonacci series is : 6765 $ ./a.out Enter which fibonacci number(nth) you want to print : 0 0th Fibonacci Number in Fibonacci Series is : 0 $ |
What if the user enters a negative number
|
1 2 3 4 |
$ ./a.out Enter which fibonacci number(nth) you want to print : -13 Invalid Input, Please provide valid number $ |
The program is displaying an error message.
📢 If you try to calculate the large (nth – above 46th – depending upon Integer size) Fibonacci number, Then we might face the Integer Overflow problem. So Make sure to large datatype for variables i, j, and k.
For example, if you try to generate the
50th Fibonacci Number, You will get invalid values (Invalid valid means negative values or wrong values ) you can overcome this problem by using
long long Integer for
i,
j,
k variables.
In the Above program, We used
Long int, So its max size is around
2 Giga +. So up to the
46th Fibonacci number we get the correct values but when we try to calculate the 47th Fibonacci number, We will get Negative values. Actually, the 47th Fibonacci number is 2971215073.
nth Fibonacci Number program using while loop:
The program algorithm is not going to change. We have used the for loop in the above example, Now we are going to use the while loop instead.
We also add a goto statement to take the control back to the input step. So that the user can provide the input again. ( Presently we simply terminating the program.)
Here is the modified program
|
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 |
/* C program to calculate nth Fibonacci Number using while loop */ #include<stdio.h> int main() { int i,j,k,num,cnt; START: printf("Enter which fibonacci number(nth) you want to print : "); scanf("%d",&num); // check 'num', display error on Invalid input. // Our Fibonacci numbers starts from '0', So don't allow negative numbers. if(num < 0) { printf("Invalid Input, Please provide valid number \n"); goto START; } /* * First two numbers in Fibonacci Series is 0 and 1 * so We are using the variables 'i' and 'j' as the * first two numbers in Fibonacci Series */ i=0; j=1; k=i+j; // Check if if(num==0) { printf("0th Fibonacci Number in Fibonacci Series is : %d\n",i); return 0; } if(num==1) { printf("1st Fibonacci Number in Fibonacci Series is : %d\n",j); return 0; } /* * 'cnt' is 1 because we already have i and j as first two numbers i.e 0th and 1st numbers * So our 'cnt' is starting from '0', goes uptp 'num-1' */ cnt=1; while(cnt < num-1) { i=j; j=k; // calculate next fibonacci number by adding new 'i' and 'j' k=i+j; //increment the counter 'cnt' cnt++; } printf("%d(th) Fibonacci Number in Fibonacci series is : %d\n",num,k); return 0; } |
Program Output:
Compile and run the C Program.
|
1 2 3 4 5 6 7 8 9 10 11 |
$ gcc nth-fib.c $ ./a.out Enter which fibonacci number(nth) you want to print : 4 4(th) Fibonacci Number in Fibonacci series is : 3 $ ./a.out Enter which fibonacci number(nth) you want to print : 2 2(th) Fibonacci Number in Fibonacci series is : 1 $ ./a.out Enter which fibonacci number(nth) you want to print : 10 10(th) Fibonacci Number in Fibonacci series is : 55 $ |
As you can see from the above output, We are getting the desired output.
Let’s look at how the program behaves to negative numbers.
|
1 2 3 4 5 6 7 8 |
$ ./a.out Enter which fibonacci number(nth) you want to print : -23 Invalid Input, Please provide valid number Enter which fibonacci number(nth) you want to print : -4 Invalid Input, Please provide valid number Enter which fibonacci number(nth) you want to print : 9 9(th) Fibonacci Number in Fibonacci series is : 34 $ |
As expected, The program is showing the error message and asking for the input again.
Related Articles :
- C Program to calculate first n Fibonacci Numbers.
- Program to calculate Fibonacci numbers up to Given Number.
- C program to calculate Grade of Student.
- Bitwise OR Operator Tutorial with Examples.
