Java Program to Implement Efficient O(log n) Fibonacci Generator

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.

  1. /**
  2.  ** Java Program to Implement Efficient O(log n) Fibonacci generator 
  3.  **/
  4.  
  5. import java.util.Scanner;
  6. import java.math.BigInteger;
  7.  
  8. /** Class FibonacciGenerator **/
  9. public class FibonacciGenerator
  10. {
  11.     /** function to generate nth fibonacci number **/
  12.     public void genFib(long n)
  13.     {
  14.         BigInteger arr1[][] = {{BigInteger.ONE, BigInteger.ONE}, {BigInteger.ONE, BigInteger.ZERO}};
  15.         if (n == 0)
  16.             System.out.println("\nFirst Fibonacci number = 0");
  17.         else
  18.         {
  19.             power(arr1, n - 1);          
  20.               System.out.println("\n"+ n +" th Fibonacci number = "+ arr1[0][0]);
  21.         }          
  22.     }
  23.     /** function raise matrix to power n recursively **/    
  24.     private void power(BigInteger arr1[][], long n)
  25.     {
  26.         if (n == 0 || n == 1)
  27.             return;
  28.         BigInteger arr2[][] = {{BigInteger.ONE, BigInteger.ONE}, {BigInteger.ONE, BigInteger.ZERO}};     
  29.         power(arr1, n / 2);
  30.         multiply(arr1, arr1);     
  31.         if (n % 2 != 0)
  32.             multiply(arr1, arr2);
  33.     }     
  34.     /** function to multiply two 2 d matrices **/
  35.     private void multiply(BigInteger arr1[][], BigInteger arr2[][])
  36.     {
  37.         BigInteger x = (arr1[0][0].multiply(arr2[0][0])).add(arr1[0][1].multiply(arr2[1][0]));
  38.         BigInteger y = (arr1[0][0].multiply(arr2[0][1])).add(arr1[0][1].multiply(arr2[1][1]));
  39.         BigInteger z = (arr1[1][0].multiply(arr2[0][0])).add(arr1[1][1].multiply(arr2[1][0]));
  40.         BigInteger w = (arr1[1][0].multiply(arr2[0][1])).add(arr1[1][1].multiply(arr2[1][1])); 
  41.         arr1[0][0] = x;
  42.         arr1[0][1] = y;
  43.         arr1[1][0] = z;
  44.         arr1[1][1] = w;     
  45.     }
  46.     /** Main function **/
  47.     public static void main(String[] args) 
  48.     {
  49.         Scanner scan = new Scanner(System.in);
  50.         System.out.println("Efficient Fibonacci Generator\n");
  51.         System.out.println("Enter number n to find nth fibonacci number\n");
  52.         long n = scan.nextLong();
  53.         FibonacciGenerator fg = new FibonacciGenerator();
  54.         fg.genFib(n);
  55.     }
  56. }

Efficient Fibonacci Generator
 
Enter number n to find nth fibonacci number
 
1000
 
1000 th Fibonacci number = 43466557686937456435688527675040625802564660517371780
40248172908953655541794905189040387984007925516929592259308032263477520968962323
9873322471161642996440906533187938298969649928516003704476137795166849228875

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.