fork download
copy 
  1. /**
  2.  * Find the Nth Fibbonacci Number using Matrix Exponentiation Method
  3.  * @author PRATEEK
  4.  *
  5.  */
  6. class FibbonacciNumber {
  7.  
  8. 	private static int[][] F = { { 1, 1 }, { 1, 0 } }; // will change , and will capture rsult here
  9. 	private static int[][] I = { { 1, 1 }, { 1, 0 } }; //will remain fixed
  10.  
  11. 	public static int fib(int n){
  12. 		if(n==0)
  13. 			return 0;
  14. 		power(F,n-1);
  15.  
  16. 		return F[0][0];
  17. 	}
  18.  
  19. 	/**
  20. 	 * Calculates F to the power n
  21. 	 * @param F
  22. 	 * @param n
  23. 	 */
  24. 	private static void power(int[][] F, int n) {
  25. 		if(n==0 || n==1)
  26. 			return;
  27.  
  28. 		power(F,n/2);
  29. 		multiplyMatrix(F,F);
  30.  
  31. 		if(n%2!=0)
  32. 			multiplyMatrix(F, I);
  33. 	}
  34.  
  35. 	/**
  36. 	 * Multiples Matrixes of size 2X2
  37. 	 */
  38. 	public static int[][] multiplyMatrix(int[][] A, int[][] B)
  39. 	{
  40. 		  int x =  A[0][0]*B[0][0] + A[0][1]*B[1][0];
  41. 		  int y =  A[0][0]*B[0][1] + A[0][1]*B[1][1];
  42. 		  int z =  A[1][0]*B[0][0] + A[1][1]*B[1][0];
  43. 		  int w =  A[1][0]*B[0][1] + A[1][1]*B[1][1];
  44.  
  45. 		  A[0][0] = x;
  46. 		  A[0][1] = y;
  47. 		  A[1][0] = z;
  48. 		  A[1][1] = w;
  49.  
  50. 		  return A;
  51. 	}
  52.  
  53. 	public static void main(String[] args) {
  54. 		//1,1,2,3,5,8,13,21,34,55,89...
  55. 		int n = 8;
  56. 		System.out.println(n + "--->" + fib(n));
  57. 	}
  58.  
  59. 	/**
  60. 	 * recursiver approach , exponential Complexity
  61. 	 * @param n
  62. 	 * @return
  63. 	 */
  64. 	public static int fib1(int n)
  65. 	{
  66. 		if(n<=1)
  67. 			return n;
  68. 		return fib1(n-1) + fib(n-2);
  69. 	}
  70.  
  71. 	/**
  72. 	 * DP approach , O(n) complexity
  73. 	 */
  74. 	public static int fib2(int n)
  75. 	{
  76. 		if(n==0)
  77. 			return 0;
  78. 		int old1=0 , old2=1 , curr,i=2;
  79. 		for(;i<=n;i++)
  80. 		{
  81. 			curr = old1 + old2;
  82. 			old1= old2;
  83. 			old2 = curr;
  84. 		}
  85. 		return old2;
  86. 	}
  87. }
  88.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8--->21
https://ideone.com/4R2SVc
Fibbonaci number in O(log n) time
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!