Fibonacci sequence computation is a classical problem. Traditionally, methods like recursive and iterative algorithms have been employed, but they tend to exhibit exponential time complexity, which becomes impractical for large inputs. The program given below introduces a novel approach to compute the nth Fibonacci number efficiently using matrix exponentiation in Java.
Matrix Exponentiation for Fibonacci Computation:
The crux of the proposed solution lies in representing the Fibonacci recurrence relation as a matrix exponentiation problem. Consider the matrix M = [[1, 1], [1, 0]], and let F(n) represent the nth Fibonacci number. By raising the matrix M to the power of n-1 using recursive matrix exponentiation, we obtain the desired result in logarithmic time complexity.
public class NthFibonacci {
static final int MOD = (int) 1e9 + 7;
//Method to perform matrix multiplication
static long[][] multiply(long[][] A, long[][] B) {
int rowA = A.length;
int colA = A[0].length;
int colB = B[0].length;
long[][] C = new long[rowA][colB];
for (int i = 0; i < rowA; i++) {
for (int j = 0; j < colB; j++) {
for (int k = 0; k < colA; k++) {
C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % MOD) % MOD;
}
}
}
return C;
}
//Method to perform matrix exponentiation
static long[][] power(long[][] M, int n) {
if (n == 1) return M;
long[][] half = power(M, n / 2);
long[][] result = multiply(half, half);
if (n % 2 == 1) result = multiply(result, M);
return result;
}
//Method to find the Nth Fibonacci number using matrix exponentiation
public static int fibonacciNumber(int n) {
if (n <= 1) return n;
long[][] M = {{1, 1}, {1, 0}};
long[][] result = power(M, n – 1);
return (int) result[0][0];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(fibonacciNumber(n));
scanner.close();
}
}
The _power _method calculates the matrix raised to the power of N. It uses recursion and optimizes the process by halving the exponent at each step. The method called _multiply _performs matrix multiplication. This is a key operation in the matrix exponentiation technique.
This program efficiently calculates the nth Fibonacci number using matrix exponentiation, which has a time complexity of O(log n), making it much faster than the traditional recursive approach with O(2^n) time complexity.
