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 Implement Double Order Traversal of a Binary Tree
Java Program to Give an Implementation of the Traditional Chinese Postman Problem
Java Program to Check if a Point d lies Inside or Outside a Circle Defined by Points a, b, c in a Pl...
Create a Custom Exception in Java
HttpClient with SSL
Write/Read cookies using HTTP and Read a file from the internet
Hướng dẫn tạo và sử dụng ThreadPool trong Java
Java Program to Implement Sorted Circular Doubly Linked List
Getting Started with GraphQL and Spring Boot
Allow user:password in URL
Spring MVC + Thymeleaf 3.0: New Features
Ép kiểu trong Java (Type casting)
Spring REST API + OAuth2 + Angular (using the Spring Security OAuth legacy stack)
Configuring a DataSource Programmatically in Spring Boot
Java Program to Implement Skip List
Java Program to Implement Unrolled Linked List
Java Program to Generate a Random Subset by Coin Flipping
Java Program to Emulate N Dice Roller
Introduction to Spring Data MongoDB
An Intro to Spring Cloud Security
Spring Data Java 8 Support
Creating a Custom Starter with Spring Boot
Java – InputStream to Reader
Java Program to Perform Left Rotation on a Binary Search Tree
Java Program to Solve the Fractional Knapsack Problem
A Guide to Java SynchronousQueue
Uploading MultipartFile with Spring RestTemplate
Debug a JavaMail Program
Java Program to Implement Best-First Search
Java Optional as Return Type
Java Program to Implement Queue using Linked List
Java Program to Implement Fibonacci Heap