This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.

Try again

The second order matrix of the Fibonacci sequence

So I’m going to solve for the second order matrix A of the Fibonacci sequence.

Known, F (3) = F (2) + F (1), F (4) = F (3) + F (2) = 2 F (2) + F (1), F (2) = 1, F (1) = 1.

Substituting the rule of the second-order constant coefficient homogeneous linear recursive sequence, we can get:

|F(3) F(2)| = |F(2) F(1)| * A

|F(4) F(3)| = |F(3) F(2)| * A

Here | F (2) and F (1) | | F (3) F (2) | is a matrix,

The second order matrix A is zero

||a b|,

|c d||

We convert F(3), F(2), F(1) into the numbers 2, 1, 1.

|F(3) F(2)| = |1 1| * A = | a + c , b + d|

|F(4) F(3)| = |2 1| * A = | 2a + c, 2b + d |

So we have four equations:

A + c = 2, b + d = 1, 2a + c = 3, 2b + d = 2.

calculated

a = 1, b = 1, c = 1, d = 0.

So our matrix A is zero

| | | 1 1,

1 0 | | |

With matrix A, we can dramatically reduce the time complexity by moving bits, which is log(n).

So the last question is, what is the initial base?

Initial cardinality

If we were doing X to the N, we could have let the caller do the input, but this is Fibonacci, so we have to figure out the cardinality.

We are in accordance with the second-order constant coefficient homogeneous linear recursion sequence rule: | F (n) (n – 1) F | | = F (n – 1) * F (n – 2) | A, can we come to the base is used (2) F (1) | | F.

But, we have to create a matrix multiplication method, if use base: (1) | | F (2) F, that we will not be able to write a generic methods, so we also want to find a second order matrix as a base.

As a result, you can use the | | F (2), F (1) | | 0 0 | | for use as a base, we only take the value of the first column.

All right, let’s start coding.

Public int Fibonacci (int n) {if (n <= 2) {return 1; if (n <= 2) {return 1; } int[][] base = {{1, 1}, {0, 0}}; int[][] A = {{1, 1}, {1, 0}}; base = multiMatrix(base, A, n - 2); return base[0][0]; } /** * multiMatrix(int[] multiMatrix(int[]] multiMatrix(]) [] multiMatrix(]) [] Base, int[][] A, int n) {// We can copy calculationPower1, only temp = base is changed to = A, Int [][] temp = A; for (; n ! = 0; n = n >> 1) { if ((n & 1) ! = 0) { base = multiMatrix(base, temp); } temp = multiMatrix(temp, temp); } return base; Private int[] multiMatrix(int[][] multiMatrix(int[]] base, int[][] A) { int[][] ints = new int[base.length][base[0].length]; for (int i = 0; i < ints.length; i++) { for (int j=0; j<ints[0].length; j++){ for (int k=0; k<A[0].length; k++){ ints[i][j] += base[i][k] * A[k][j]; } } } return ints; }Copy the code

Because my personal level is limited, the method of multiplying two matrices, I copied the writing method of others, and then modified some part after my own understanding, I can not calculate the algorithm from matrix multiplication, here I can only combine the algorithm and matrix multiplication, deduce how the algorithm is calculated.

Remember the matrix multiplication?

|

|a1 , a2|,

|a3 , a4|

| × |

|b1 , b2|,

|b3 , b4|

| = |

|a1 b1 + a2 b3 , a1 b2 + a2 b4|,

|a3 b1 + a4 b3 , a3 b2 + a4 b4||

Here we consider an array a, see the bn as array b, the back the | a1 + a2 b1 b3… | as an array of res.

res =

|a1 b1 + a2 b3 , a1 b2 + a2 b4|,

|a3 b1 + a4 b3 , a3 b2 + a4 b4|

= >

|a[0][0] b[0][0] + a[0][1] b[1][0] , a[0][0] b[0][1] + a[0][1] b[1][1]|,

|a[1][0] b[0][0] + a[1][1] b[1][0] , a[1][0] b[0][1] + a[1][1] b[1][1]|

MultiMatrix (this part speaks of multiplication of two matrices) is actually to fill in the array bit by bit, res[0][0] -> RES [0][1] -> RES [1][0] -> RES [1][1]

res[0][0] = a[0][0] b[0][0] + a[0][1] b[1][0],

res[0][1] = a[0][0] b[0][1] + a[0][1] b[1][1],

res[1][0] = a[1][0] b[0][0] + a[1][1] b[1][0],

res[1][1] = a[1][0] b[0][1] + a[1][1] b[1][1].

A rule can be drawn by visual method:

res[i][j] = a[i][0] b[0][j] + a[i][1] b[1][j]

So, how does this triple for loop compute?

The innermost for loop simplifies the a[I][0] b[0][j] + a[I][1] b[1][j] part of the loop. We can also write it in code, but then it can only be used for second-order matrix multiplication.

Execute!

You don’t have to look at it, there’s no doubt that it’s going to pass, if it’s not going to pass, I’ll write it up, okay?

But how is this running time the same as dynamic programming? !

Just calm down and learn something.

Comparison of two algorithms

How much faster is the log(n) time algorithm than the n time algorithm?

public static void main(String[] args) { Solution2 solution2 = new Solution2(); Println (" solution2.fibonacci (I)"); long startTime1 = System.nanoTime(); solution2.Fibonacci(100000000); long endTime1 = System.nanoTime(); System.out.println((endTime1 - startTime1)); Println ("solution2.fibonacci(I)"); solution2.fibonacci(I); long startTime2 = System.nanoTime(); solution2.fibonacci(100000000); long endTime2 = System.nanoTime(); System.out.println((endTime2 - startTime2)); }Copy the code

Running results:

solution2.Fibonacci(i)

36458800

solution2.fibonacci(i)

37100

982.7 times faster!!

So log n is very fast.

Well, that’s the end of the Fibonacci sequence.

Here is a programmer Xu Xiaobai, daily algorithm [is] my new open a column, primary record my daily learning algorithm, here also hope that I can stick to the daily learning algorithm, don’t know whether this article style you like, don’t mean you free praise, your thumb up, collection, and comments are after work I insist on more power.

The resources

# Intuitive understanding! You have to read introduction to Matrices and Linear Algebra.

# Optimal complexity of Fibonacci sequence algorithms ——-O (logN)

Second order constant coefficient linear homogeneous recursive sequence _GMqfrostwalker’s blog -CSDN blog

An optimal algorithm for Fibonacci sequence (O (logN))

Conversion between binary and decimal – Zhihu (Zhihu.com)