“Let n be 0. The Fibonacci number for 0 is:
Let n be 1. The Fibonacci number for 1 is:
Let n be 2. The Fibonacci number for 2 is:
Let n be 3. The Fibonacci number for 3 is:
Let n be 4. The Fibonacci number for 4 is:
Let n be 5. The Fibonacci number for 5 is:
Let n be 6. The Fibonacci number for 6 is:
Let n be 7. The Fibonacci number for 7 is:
Let n be 8. The Fibonacci number for 8 is:
Let n be 9. The Fibonacci number for 9 is:
The following table shows the first twelve Fibonacci numbers:
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
The first row gives the Fibonacci numbers. The second row gives the zero-based indexes for the corresponding array. These indexes are the different n integers, beginning from zero. It can be seen from the table that the tenth Fibonacci number is 34 + 21 = 55. Also, the eleventh Fibonacci number is, 55 + 34 = 89 .
The aim of this article is to produce a Fibonacci number in O(n) time and in constant time O(1), using the computer language C.
Fibonacci numbers are integers, beginning from 0.”
The Formula for a Fibonacci Number
As seen from the above table, the current Fibonacci number is the sum of the previous two numbers. The Fibonacci number for 0 is 0, and the Fibonacci number for 1 is 1. These first two numbers, in their order, must be accepted as such. Developing the following Fibonacci numbers, begin from there, to give 1 + 0 = 1; 1 + 1 = 2; 2 + 1 = 3, etc.
The formula for a particular Fibonacci number can be given in three lines or one line. The formula in three lines is given as follows:
This formula is the definition of a Fibonacci number.
Producing Fibonacci Numbers in O(n) Time
More than one Fibonacci number can be produced beginning from zero for a given value of n. In this case, n is the highest index plus 1 for the array – assume zero-based indexing. The Fibonacci number for i=0 is produced (i.e 0). The Fibonacci number for i=1 is then produced (i.e., 1). The Fibonacci number for i=2 is then produced next (i.e., 1 again). The Fibonacci number for i=3 is then produced (i.e., 2). The Fibonacci number for i=4 is then produced (i.e., 3). This continues until the Fibonacci number for the given number (index) of n, say 12, for the highest index of 11, is produced (89).
A C program that takes input from the keyboard and outputs it to the terminal (screen) begins with:
With this pre-processing directive, text typed on the keyboard will appear on the screen. Program output will also appear on the screen. The Fibonacci function is:
if (n > 0)
A[0] = 0;
if (n > 1)
A[1] = 1;
for (int i=2; i<n; i++) { //n=0 and n=2 have been considered
int nextNo = A[i - 1] + A[i - 2];
A[i] = nextNo;
}
}
The first two statements in the function are considered as two operations. The body of the for-loop can be considered as one operation. If n is 12, then the body of the for-loop operates 10 times because the first and second operations, for index 0 and index 1, have already taken place. This gives a time complexity of O(12), written as O(n).
Note the statement:
In the body of the for-loop. It adds the two previous Fibonacci numbers to obtain the current Fibonacci number (nextNo).
A suitable C main function for the above program is:
{
int N = 12;
int arr[12];
fibonacci(arr, N);
for (int i=0; i<N; i++)
printf("%i, ", arr[i]);
printf("\n");
return 0;
}
Producing One Fibonacci Number in Constant Time
Above, the index for the Fibonacci number, 89, is 11, and not 12, for zero-based indexing. Let 11 be n. In this case, the current Fibonacci number is 89. If n is 10, the current Fibonacci number would be 55. If n is 9, the current Fibonacci number would be 34. This continues downwards until when n is 0, the Fibonacci number would be 0.
There is a mathematical formula to obtain the current (one) Fibonacci number, given the zero-based index (number), with the variable name n. The formula is:
Note that on the right-hand side of the equation, it is not the square root of 5 that is raised to the power n; it is the expression in parentheses that is raised to the power n. There are two such expressions.
So, when n is 0, Fibn will be 0. When n is 1, Fibn will be 1. When n is 2, Fibn will be 1. When n is 3, Fibn will be 2 – and so on.
This mathematical function is one main operation, and it returns just one Fibonacci number and not a sequence of numbers corresponding to, say, index 0 to index 11. This is a constant time code. It can still be used to produce a sequence of Fibonacci numbers by just calling it over and over with different values of n, as indexes, in a program.
The time complexity for this mathematical function to produce its one Fibonacci number is O(1), constant time.
Now, this mathematical function is coded below to produce 12 Fibonacci numbers. It would use less overall time than the previous algorithm.
The code for this mathematical function to produce its one Fibonacci number is:
#include <math.h>
double fibNo(int n) {
double FibN = (pow((1+sqrt(5))/2, n) - pow((1-sqrt(5))/2, n)) / sqrt(5);
return FibN;
}
Note that the math.h library is included this time, which brings in the power (pow) and square root (sqrt) predefined functions to the program. The function produces just one Fibonacci number and not a sequence of them. A suitable main function for this code is:
{
int N = 11;
double FibN = fibNo(N);
printf("%lf\n", FibN);
return 0;
}
With an index of 11, the output is 89.000000. However, to run this program with the gcc compiler, use a command line like:
where “temp.c” is the source code, and “temp” is the compiled program. Note the use of the switch, “-lm”, where “l” is lowercase L.
Conclusion
The first Fibonacci number is 0. The second Fibonacci number is 1. The rest are gotten by adding the previous two Fibonacci numbers. Fibonacci numbers are integers. To obtain the sequence of Fibonacci numbers from zero in O(n) time, use a function with a statement like:
where nextNo is the current number for the index i, and “A” is the array to hold the Fibonacci sequence numbers. The first two numbers, 0 and 1, are produced independently.
To obtain just one Fibonacci number in O(1) time, use the math formula:
where n is the zero-based index.
Fibonacci numbers can be obtained using math matrices. However, this is a discussion for some other time.
