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:
REST Pagination in Spring
Java Program to Find Transitive Closure of a Graph
Wrapper Classes in Java
Java Program to Implement Dijkstra’s Algorithm using Priority Queue
Mapping a Dynamic JSON Object with Jackson
Java Program to Generate Random Numbers Using Multiply with Carry Method
Java Program to Implement Sorted Circular Doubly Linked List
Spring Security Authentication Provider
Inheritance and Composition (Is-a vs Has-a relationship) in Java
Java Program to Implement Caesar Cypher
Sorting Query Results with Spring Data
Overview of Spring Boot Dev Tools
Spring Boot - Exception Handling
Java Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm
Java Program to Perform Postorder Non-Recursive Traversal of a Given Binary Tree
Logout in an OAuth Secured Application
Chuyển đổi Array sang ArrayList và ngược lại
Exploring the Spring 5 WebFlux URL Matching
Java Program to Implement Suffix Array
Spring @RequestMapping New Shortcut Annotations
Java 8 Predicate Chain
Sắp xếp trong Java 8
Create a Custom Auto-Configuration with Spring Boot
How To Serialize and Deserialize Enums with Jackson
Java Program to Implement Floyd-Warshall Algorithm
Java Program to Use rand and srand Functions
Guide to CountDownLatch in Java
Java Program to Implement Sieve Of Atkin
Spring Cloud Bus
Java Program to Implement LinkedBlockingDeque API
Testing an OAuth Secured API with Spring MVC
How to Set TLS Version in Apache HttpClient