This is a Java Program to Implement Efficient O(log n) Fibonacci generator . This is a program to generate nth fibonacci number with O(log n) complexity.
Here is the source code of the Java Program to Implement Efficient O(log n) Fibonacci generator . The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** ** Java Program to Implement Efficient O(log n) Fibonacci generator **/ import java.util.Scanner; import java.math.BigInteger; /** Class FibonacciGenerator **/ public class FibonacciGenerator { /** function to generate nth fibonacci number **/ public void genFib(long n) { BigInteger arr1[][] = {{BigInteger.ONE, BigInteger.ONE}, {BigInteger.ONE, BigInteger.ZERO}}; if (n == 0) System.out.println("\nFirst Fibonacci number = 0"); else { power(arr1, n - 1); System.out.println("\n"+ n +" th Fibonacci number = "+ arr1[0][0]); } } /** function raise matrix to power n recursively **/ private void power(BigInteger arr1[][], long n) { if (n == 0 || n == 1) return; BigInteger arr2[][] = {{BigInteger.ONE, BigInteger.ONE}, {BigInteger.ONE, BigInteger.ZERO}}; power(arr1, n / 2); multiply(arr1, arr1); if (n % 2 != 0) multiply(arr1, arr2); } /** function to multiply two 2 d matrices **/ private void multiply(BigInteger arr1[][], BigInteger arr2[][]) { BigInteger x = (arr1[0][0].multiply(arr2[0][0])).add(arr1[0][1].multiply(arr2[1][0])); BigInteger y = (arr1[0][0].multiply(arr2[0][1])).add(arr1[0][1].multiply(arr2[1][1])); BigInteger z = (arr1[1][0].multiply(arr2[0][0])).add(arr1[1][1].multiply(arr2[1][0])); BigInteger w = (arr1[1][0].multiply(arr2[0][1])).add(arr1[1][1].multiply(arr2[1][1])); arr1[0][0] = x; arr1[0][1] = y; arr1[1][0] = z; arr1[1][1] = w; } /** Main function **/ public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Efficient Fibonacci Generator\n"); System.out.println("Enter number n to find nth fibonacci number\n"); long n = scan.nextLong(); FibonacciGenerator fg = new FibonacciGenerator(); fg.genFib(n); } }
Output:
Efficient Fibonacci Generator Enter number n to find nth fibonacci number 1000 1000 th Fibonacci number = 43466557686937456435688527675040625802564660517371780 40248172908953655541794905189040387984007925516929592259308032263477520968962323 9873322471161642996440906533187938298969649928516003704476137795166849228875
Related posts:
Hướng dẫn Java Design Pattern – Iterator
Các chương trình minh họa sử dụng Cấu trúc điều khiển trong Java
Hướng dẫn Java Design Pattern – Service Locator
Spring Data Reactive Repositories with MongoDB
Jackson – Marshall String to JsonNode
Adding Parameters to HttpClient Requests
Java – Try with Resources
Giới thiệu Java 8
The Modulo Operator in Java
Hashtable trong java
Java Program to Generate Random Hexadecimal Byte
Refactoring Design Pattern với tính năng mới trong Java 8
Spring Boot - Google Cloud Platform
Call Methods at Runtime Using Java Reflection
Java Program to Find All Pairs Shortest Path
A Guide to Concurrent Queues in Java
Quick Guide to @RestClientTest in Spring Boot
Intro to Inversion of Control and Dependency Injection with Spring
Creating a Generic Array in Java
Practical Java Examples of the Big O Notation
How to Get a Name of a Method Being Executed?
Java Program to Generate a Graph for a Given Fixed Degree Sequence
Java Program to implement Bit Set
Java Program to Implement Stack using Two Queues
Spring WebClient Requests with Parameters
Java List UnsupportedOperationException
Java Program to Implement Sorted Doubly Linked List
Copy a List to Another List in Java
REST Pagination in Spring
Java Program to Solve Travelling Salesman Problem for Unweighted Graph
Java Program to Implement Radix Sort
Java Program to Implement Euclid GCD Algorithm