Fibonacci Numbers in Java Language

September 30, 2022 | by Arround The Web | No comments

Fibonacci Numbers in Java Language

The Fibonacci numbers is a particular sequence of positive (whole) integers, beginning from zero to positive infinity. The current Fibonacci number is obtained by adding the immediate previous two Fibonacci numbers. The immediate previous two Fibonacci numbers are not just any numbers.

In fact, the first two Fibonacci numbers are predefined. The first Fibonacci number is 0 and the second Fibonacci number is 1. With zero-based indexing and assuming Fibonacci numbers are in an array, then:

at index 0, the Fibonacci number is 0, (predefined);

at index 1, the Fibonacci number is 1, (predefined);

at index 2, the Fibonacci number is 1 = 1 + 0, (by definition);

at index 3, the Fibonacci number is 2 = 1 + 1, (by definition);

at index 4, the Fibonacci number is 3 = 2 + 1, (by definition);

at index 5, the Fibonacci number is 5 = 3 + 2, (by definition);

at index 6, the Fibonacci number is 8 = 5 + 3, (by definition);

at index 7, the Fibonacci number is 13 = 8 + 5, (by definition);

at index 8, the Fibonacci number is 21 = 13 + 8, (by definition);

at index 9, the Fibonacci number is 34 = 21 + 13, (by definition);

and so on.

In programming, the variable n, and not i is used for the zero-based indexes for these Fibonacci numbers. And with that, the first twelve Fibonacci numbers are:

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 second row in the table gives the zero-based indexes, each of which would have the variable n in programming. The first row gives the corresponding Fibonacci numbers. So, Fibonacci numbers are not just any numbers. The core definition begins with 0, for the first Fibonacci number and 1 for the second Fibonacci number. The rest of the numbers are produced from there.

Fibonacci numbers can be produced in O(n) time and also in O(1) time. For O(n) time, if n is 12 for example, then the first twelve Fibonacci numbers would be produced. For O(1) time, only one Fibonacci number is produced. For example, if n is 6, then the Fibonacci number 8 would be produced.

This article explains these two ways of producing Fibonacci numbers in Java.

Formula for a Fibonacci Number

There is a mathematical formula for a Fibonacci number. This formula can be written in three lines or one line. In three lines, it is written as:

where F_n is the Fibonacci number at the zero-based n^th index. This is how Fibonacci number is defined.

Producing Fibonacci Numbers in O(n) Time

If Fibonacci numbers are to be produced in O(3) times, the numbers, 0, 1, 1 would be produced; those are the first three Fibonacci numbers. The last zero-based n^th index here, is 2. If Fibonacci numbers are to be produced in O(7) times, the numbers, 0, 1, 1, 2, 3, 5, 8 would be produced; those are the first seven Fibonacci numbers. The last zero-based n^th index here, is 6. If Fibonacci numbers are to be produced in O(n) times, the numbers, 0, 1, 1, 2, 3, 5, 8 – – -, would be produced; those are the first n Fibonacci numbers. The last zero-based n^th index here is n-1.

The Java method in a class to produce the first n Fibonacci numbers is:

class Fibonacci {
void fibonacci(int[] P) {
int n = P.length;
if (n > 0)
P[0] = 0;
if (n > 1)
P[1] = 1;
for (int i=2; i<n; i++) { //n=0 and n=2 have been considered
int currNo = P[i - 1] + P[i - 2];
P[i] = currNo;
}
}
}

The class, Fibonacci is private. The fibonacci() method takes the array P and returns void. The method begins by determining the length of the array. This length of n is the number of Fibonacci numbers required. The first and second Fibonacci numbers are determined explicitly and put into the first and second positions in the array.

The rest of the Fibonacci numbers beginning from the third (index, n = 2) are determined in a for-loop and put in their positions in the array. So, the function has to return void. The principal statement in the for-loop adds the previous two numbers.

The index variable, i, has been used instead of n, for the purpose of clarity.

A suitable Java Main class (with the Java main method) is:

public class Main{
public static void main(String args[]){
int m = 12;
int[] arr = new int[m];
Fibonacci obj = new Fibonacci();
obj.fibonacci(arr);
for (int i=0; i<m; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}

After the numbers have been produced by the fibonacci() method, the Java main method reads them out.

Producing One Fibonacci Number in Constant Time

There is a mathematical formula that can be used to produce a Fibonacci number, when given the corresponding zero-based index, n. The formula is:

where n is the zero-based index and Fib_n is the corresponding Fibonacci number. 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 of such expressions.

If n is 0, Fib_n would be 0. If n is 1, Fib_n would be 1. If n is 2, Fib_n would be 1. If n is 3, Fib_n would be 2. If n is 4, Fib_n would be 3 – and so on. The reader can verify this formula mathematically, by substituting different values for n and evaluating.

When coded, this formula would produce just one Fibonacci number for n. If more than one Fibonacci numbers are required, the code for the formula has to be called once for each of the different corresponding indexes.

In Java, the method to produce just one Fibonacci number is:

import java.lang.*;

class Fib {
double fibNo(int n) {
double FibN = (Math.pow((1+Math.sqrt(5))/2, n) –Math.pow((1-Math.sqrt(5))/2, n)) / Math.sqrt(5);
return FibN;
}
}

The java.lang.* package had to be imported at the beginning of the program. This is because the package has the Math class, which has the power (pow) and square root (sqrt) methods. The custom Java method here implements the math formula directly.

The time complexity for this function is O(1), constant tame of one main operation. A suitable Java Main class, with Java main method for the above method is:

public class Main{
public static void main(String args[]){
int N = 11;
Fib obj = new Fib();
double ret = obj.fibNo(N);
System.out.println(ret);
}
}

The index n = 11 is sent and the Fibonacci number, 89 is returned. The output is:

89.00000000000003

The unnecessary decimal digits can be removed, but that is a discussion for some other time.

Conclusion

Fibonacci numbers are a particular sequence of whole numbers. To obtain the current number, add the immediate previous two corresponding numbers. The first two Fibonacci numbers, 0 followed by 1, are pre-declared, for the whole sequence. The rest of the Fibonacci numbers are produced from there.

To produce Fibonacci numbers from index 2, to that which corresponds to index n-1, use a for-loop with the principal statement:

int currNo = P[i - 1] + P[i – 2];

where currNo is the current Fibonacci number and P is the array to store the n numbers.

To produce just one Fibonacci number from any zero-based index n, use the mathematical formula:

Source: linuxhint.com