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:
Java Program to Generate Random Numbers Using Multiply with Carry Method
Spring Boot - Quick Start
Query Entities by Dates and Times with Spring Data JPA
Call Methods at Runtime Using Java Reflection
Hướng dẫn Java Design Pattern – Intercepting Filter
Immutable ArrayList in Java
Java Program to Perform Preorder Non-Recursive Traversal of a Given Binary Tree
Collect a Java Stream to an Immutable Collection
Write/Read cookies using HTTP and Read a file from the internet
Properties with Spring and Spring Boot
Spring Boot - Zuul Proxy Server and Routing
List Interface trong Java
Filtering and Transforming Collections in Guava
Comparing Dates in Java
Java Program to Implement Trie
Java Program to Construct an Expression Tree for an Infix Expression
More Jackson Annotations
Spring Cloud – Adding Angular
Introduction to the Java ArrayDeque
Java Program to Find Shortest Path Between All Vertices Using Floyd-Warshall’s Algorithm
Java Program to Implement Booth Algorithm
Binary Numbers in Java
Java Program to Implement Expression Tree
Upload and Display Excel Files with Spring MVC
Java Program to Implement Pollard Rho Algorithm
Entity To DTO Conversion for a Spring REST API
Java Program to Implement LinkedHashMap API
LinkedHashSet trong java
Receive email using POP3
Spring Boot - Bootstrapping
Login For a Spring Web App – Error Handling and Localization
Java Program to Construct an Expression Tree for an Postfix Expression