public class FibonacciMatrixMultiplication { static int fibonacciNumber(int n) { int A[][] = { { 1, 1 }, { 1, 0 } }; if (n == 0) return 0; power(A, n - 1); return A[0][0]; } /* * Helper function that multiplies 2 matrices X and Y of size 2x2, and puts * the multiplication result back in X[][] */ static void multiply(int X[][], int Y[][]) { int x = X[0][0] * Y[0][0] + X[0][1] * Y[1][0]; int y = X[0][0] * Y[0][1] + X[0][1] * Y[1][1]; int z = X[1][0] * Y[0][0] + X[1][1] * Y[1][0]; int w = X[1][0] * Y[0][1] + X[1][1] * Y[1][1]; X[0][0] = x; X[0][1] = y; X[1][0] = z; X[1][1] = w; } /* * Helper function that calculates X[][] raise to the power n and puts the * result in X[][] */ static void power(int X[][], int n) { int i; int A[][] = { { 1, 1 }, { 1, 0 } }; // n - 1 times multiply the matrix to {{1,0},{0,1}} for (i = 2; i <= n; i++) { multiply(X, A); } } /** * @param args */ public static void main(String[] args) { int n = 10; System.out.println("Fibonacci number no." + n + " is " + fibonacciNumber(n)); } }

For more Fibonacci number problems you can visit "Fibonacci numbers - 4 solutions"

It's not 0(log(N)), it's O(N)

ReplyDeleteYou need to divide N by 2 each time to reduce the the problem 2 times on each iteration.

Here u pick all n-th before the one you are looking for, so it's O(N)

Yes Arieel, you are right - it is O(N). The text of the hyperlink is changed.

DeleteThanks!

This is an O(logN) solutions :

ReplyDeletehttp://censore.blogspot.in/2014/10/fibonacci-series-with-matrix.html

Great blog post and really helpful and your blog are very interesting and inspiring. midnightinfo

ReplyDelete