Matrix fast power

Counting

seek a n a^n an.

Obviously, a simple way is: loop n n n times, multiply the results cumulatively, and the time complexity is O ( n ) O(n) O(n) .

You can consider n n n is expressed in binary form:
n = a 0 ⋅ 2 0 + a 1 ⋅ 2 1 + ... a n − 1 ⋅ 2 n − 1 + a n ⋅ 2 n , a i ∈ { 0 , 1 } n = a_0\cdot 2^0 + a_1\cdot 2^1 + \ldots a_{n-1}\cdot 2^{n-1} + a_n\cdot 2^n, a_i\in\{0, 1\} n=a0​⋅20+a1​⋅21+...an−1​⋅2n−1+an​⋅2n,ai​∈{0,1}

Obviously, the sequence a n a n − 1 ... a 1 a 0 a_na_{n-1}\ldots a_1a_0 An − an − 1... a1 − a0 yes n n Binary representation of n.

So,
a n = a a 0 ⋅ 2 0 + a 1 ⋅ 2 1 + ... a n − 1 ⋅ 2 n − 1 + a n ⋅ 2 n a^n = a^{a_0\cdot 2^0 + a_1\cdot 2^1 + \ldots a_{n-1}\cdot 2^{n-1} + a_n\cdot 2^n} an=aa0​⋅20+a1​⋅21+...an−1​⋅2n−1+an​⋅2n

It can be written as:
a n = ∏ i = 0 n a a i ⋅ 2 i a^n = \prod_{i=0}^na^{a_i\cdot 2^i} an=i=0∏n​aai​⋅2i

When a i = 0 a_i = 0 When ai = 0, a a i ⋅ 2 i = 1 a^{a_i\cdot 2^i} = 1 aai ⋅ 2i=1, then this term is equivalent to No.
When a i = 1 a_i = 1 When ai = 1, a a i ⋅ 2 i = a 2 i a^{a_i\cdot 2^i} = a^{2^i} aai ⋅ 2i=a2i, obviously 2 i 2^i 2i can be from 2 i − 1 2^{i-1} 2i − 1 is obtained, so a 2 i = a 2 i − 1 ∗ a 2 i − 1 a^{2^i} = a^{2^{i-1}} * a^{2^{i-1}} a2i=a2i−1∗a2i−1.

We just need to n n If the current bit is 1 and RET is the final result, then ret = ret* a 2 i a^{2^i} a2i. Save with a variable a 2 i − 1 a^{2^{i-1}} a2i − 1, which can be expressed by squaring this variable each time a 2 i a^{2^{i}} a2i.

code implementation

long long quick_pow(long long base, long long n){
long long ret = 1;
while (n){
if (n & 1){
ret *= base;
}
base *= base;
n >>= 1;
}
return ret;
}

Time complexity: O ( l o g n ) O(logn) O(logn)
Space complexity: O ( 1 ) O(1) O(1)

Matrix fast power

seek A n A^n An , A A A is a matrix.

If A A A is a number, then it becomes a fast power problem.

n n n can still be written in binary form. Looking back on the thinking process of fast power, in fact, we can A A A as a whole, the problems to be solved are ret *= base and base *= base. This base is in the fast power a a a. In fast power of matrix A A A . For numbers a a A is digital multiplication for a matrix A A A, obviously, is matrix multiplication.

We first overload the operator * to realize matrix multiplication. We might as well use a two-dimensional vector to represent the matrix.

The code is as follows:

vector<vector<int>> operator * (vector<vector<int>>& m1, vector<vector<int>>& m2){
vector<vector<int>> ret;

int m1_n = m1.size(), m1_m = m1.size();
int m2_n = m2.size(), m2_m = m2.size();

if (m1_m != m2_n){
return ret;
}

ret.assign(m1_n, vector<int>(m2_m, 0));

for (int i = 0; i < m1_n; i ++){
for (int j = 0; j < m2_m; j ++){
for (int k = 0; k < m1_m; k ++){
ret[i][j] += m1[i][k] * m2[k][j];
}
}
}

return ret;
}

Then, put the fast power a a a replace with A A A, that is, replace the base with vector < vector < int > >

The matrix fast power code is as follows:

vector<vector<int>> quick_matrix_pow(vector<vector<int>> m, int n){
vector<vector<int>> ret;
if (m.size() != m.size()){
return ret;
}

ret.resize(m.size(), vector<int>(m.size()));

for (int i = 0; i < m.size(); i ++){
ret[i][i] = 1;
}

while (n){
if (n & 1){
ret = ret * m;
}
m = m * m;
n >>= 1;
}

return ret;
}

Time complexity: O ( l o g n ) ∗ O ( Moment front ride method ) O (logn) * O (matrix multiplication) O(logn) * O (matrix multiplication)
Space complexity: O ( square front large Small 2 ) O (square array size ^ 2) O (square array size 2)

Note: for the implementation of matrix multiplication, matrices m1 and m2 may not be square matrices. The matrix in the fast power of the matrix must be a square matrix.

Overall code

#include<bits/stdc++.h>

using namespace std;

long long quick_pow(long long base, long long n){
long long ret = 1;
while (n){
if (n & 1){
ret *= base;
}
base *= base;
n >>= 1;
}
return ret;
}

vector<vector<int>> operator * (vector<vector<int>>& m1, vector<vector<int>>& m2){
vector<vector<int>> ret;

int m1_n = m1.size(), m1_m = m1.size();
int m2_n = m2.size(), m2_m = m2.size();

if (m1_m != m2_n){
return ret;
}

ret.assign(m1_n, vector<int>(m2_m, 0));

for (int i = 0; i < m1_n; i ++){
for (int j = 0; j < m2_m; j ++){
for (int k = 0; k < m1_m; k ++){
ret[i][j] += m1[i][k] * m2[k][j];
}
}
}

return ret;
}

vector<vector<int>> quick_matrix_pow(vector<vector<int>> m, int n){
vector<vector<int>> ret;
if (m.size() != m.size()){
return ret;
}

ret.resize(m.size(), vector<int>(m.size()));

for (int i = 0; i < m.size(); i ++){
ret[i][i] = 1;
}

while (n){
if (n & 1){
ret = ret * m;
}
m = m * m;
n >>= 1;
}

return ret;
}

int main(){
cout << quick_pow(2, 31) << endl;

cout << "------------" << endl;

vector<vector<int>> m1 = {{1, 2}, {3, 4}};
vector<vector<int>> m2 = {{4}, {5}};

auto ret = m1 * m2;

for (auto item : ret){
for (int i : item){
cout << i << " ";
}
cout << endl;
}

cout << "------------" << endl;

ret = quick_matrix_pow(m1, 8);

for (auto item : ret){
for (int i : item){
cout << i << " ";
}
cout << endl;
}

return 0;
}

2021.08.20 9:41

The Friday of the third week of temporary exercise in Yuquan community.
I'm following Li Mu's pytorch version of "hands-on learning and deep learning" these days.

I haven't written a blog for a long time. I still haven't written many documents. I feel that procrastination has become an advanced stage.

I've also learned the usage of Appium these days. It feels similar to selenium. I learned this Appium because the positioning system of the West Lake pioneer App is not compatible with the mobile phone simulator, so I can only use the real machine to check in.
It is not a wise choice to waste time in repeated check-in. Fortunately, I know some programming.
It smells good.

By the way, I'm still chasing "anti Mafia storm", a very good online play. I've always liked sun Honglei.

There is still no single dog npy. I have very little money. I want to spend it alone.

Fast power, fast improve yourself.

Added by MattG on Mon, 20 Dec 2021 23:58:11 +0200