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:
Guide to Java OutputStream
Create a Custom Auto-Configuration with Spring Boot
Hamcrest Collections Cookbook
Java Program to Implement SynchronosQueue API
Custom Error Pages with Spring MVC
Java Program to Implement the Program Used in grep/egrep/fgrep
Java Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph
Convert XML to JSON Using Jackson
Java Program to Implement Selection Sort
Lớp TreeMap trong Java
Java Program to Implement Naor-Reingold Pseudo Random Function
Java Program to Implement the RSA Algorithm
Introduction to the Java NIO Selector
Java Program to Implement a Binary Search Algorithm for a Specific Search Sequence
Circular Dependencies in Spring
Java Program to Implement the Checksum Method for Small String Messages and Detect
Lập trình mạng với java
Autoboxing và Unboxing trong Java
TreeSet và sử dụng Comparable, Comparator trong java
Java Program to Implement Repeated Squaring Algorithm
Java 8 StringJoiner
Validate email address exists or not by Java Code
An Intro to Spring Cloud Security
Java Program to Encode a Message Using Playfair Cipher
Giới thiệu JDBC Connection Pool
Allow user:password in URL
Functional Interfaces in Java 8
How to Store Duplicate Keys in a Map in Java?
Logging in Spring Boot
How to Break from Java Stream forEach
Spring’s RequestBody and ResponseBody Annotations
Java Program to Implement Interval Tree