From Fibonacci sequence to matrix fast power technique

The method of finding the matrix multiplication of Fibonacci sequence

1） Linear solution of Fibonacci sequence （O(N)） The way is very easy to understand

2) At the same time, using linear algebra , You can also rewrite another expression ：

|F(N),F(N-1)| = |F(2),F(1)| *  Of a second-order matrix N-2 Power 

3) Find this second-order matrix , And then we can get the second-order matrix as soon as possible N-2 Power

Linear solution of Fibonacci sequence

public static int f1(int n){
    
        if(n<1){
    
            return 0;
        }
        if(n==1 || n==2){
    
            return 1;
        }
        return f1(n-1)+f1(n-2);
    }

    public static int f2(int n){
    
        if(n<1){
    
            return 0;
        }
        if(n==1 || n==2){
    
            return 1;
        }
        int pre=1;
        int res=1;
        int tmp=0;
        for(int i=3; i<=n; i++){
    
            tmp=res;
            res+=pre;
            pre=tmp;
        }
        return res;
    }

Matrix multiplication solution of Fibonacci sequence

The time complexity of the above solution is O(N), But it can be optimized to O(LogN).

The recursive formula of Fibonacci sequence ：F(n)=F(n-1)+F(n-2). This recursive formula has no conditional transfer , It's a strict recurrence , So it can be optimized to O(LogN).

therefore , Next, we prove through linear algebra |F(N),F(N-1)| = |F(2),F(1)| * Of a second-order matrix N-2 Power （ Linear algebra is invented to solve the problem of strict recurrence ）

The new problem ： A matrix of n How to calculate the power fast enough ？

Solve first ： One by one n How to calculate the power fast enough .（ The essence is to use dichotomy , The key is to use binary ）

10^75
=10^(64+8+2+1)
=10^(1001011)

So the of a matrix n The same goes for the power .

package com.harrison.class15;

/** * @author Harrison * @create 2022-03-27-18:37 * @motto  looking for him for thousand times in the crowd , Suddenly look back , The man was in the dim light . */
public class Code01_FibonacciProblem {
    
    public static int f1(int n) {
    
        if (n < 1) {
    
            return 0;
        }
        if (n == 1 || n == 2) {
    
            return 1;
        }
        return f1(n - 1) + f1(n - 2);
    }

    public static int f2(int n) {
    
        if (n < 1) {
    
            return 0;
        }
        if (n == 1 || n == 2) {
    
            return 1;
        }
        int pre = 1;
        int res = 1;
        int tmp = 0;
        for (int i = 3; i <= n; i++) {
    
            tmp = res;
            res += pre;
            pre = tmp;
        }
        return res;
    }

    public static int f3(int n){
    
        if (n < 1) {
    
            return 0;
        }
        if (n == 1 || n == 2) {
    
            return 1;
        }
        int[][] base={
    
                {
    1,1},
                {
    1,0}
                };
        int[][] res=matrixPower(base,n-2);
        // |F(N),F(N-1)| = |F(2),F(1)| *  Of a second-order matrix N-2 Power 
        return res[0][0]+res[1][0];
    }

    // p： Power number 
    public static int[][] matrixPower(int[][] m, int p) {
    
        int[][] res = new int[m.length][m[0].length];
        //  The concept of identity matrix ： The right diagonal is full of 1, The rest are all 0
        //  A unit matrix  * a matrix  = a matrix 
        for (int i = 0; i < res.length; i++) {
    
            res[i][i] = 1;
        }
        // res= In the matrix 1
        int[][] t = m;//  matrix 1 Power 
        //  Yes 1 I'm going to take it , Move right after riding and throw away 
        for (; p != 0; p >>= 1) {
    
            // ( Power number  & 1) !=0  At the end of the description is 1
            if ((p & 1) != 0) {
    
                res=muliMatrix(res,t);
            }
            t=muliMatrix(t,t);
        }
        return res;
    }

    /*  After multiplying the two matrices, the result returns , Matrix multiplication yields a new matrix   The result of the first row and the first column of the new matrix is the sum of the first row of the first matrix multiplied by the first column of the second matrix  */
    public static int[][] muliMatrix(int[][] m1, int[][] m2) {
    
        int[][] res = new int[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
    
            for (int j = 0; j < m2[0].length; j++) {
    
                for (int k = 0; k < m2.length; k++) {
    
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
    
        int n = 19;
        System.out.println(f1(n));
        System.out.println(f2(n));
        System.out.println(f3(n));
        System.out.println("===");
    }
}

The final generalization conclusion ！！！

Add ： Matrix multiplication