CODEWITHSUNDEEP
c++matrixexponentiation
Jakub Sapko
Jakub Sapko

Reputation: 316

Simple matrix exponentiation in c++

So I was asked to define a matrix as:

typedef vector<double> vec;
typedef vector<vec> matrix;

and based on that write some functions like scalar multiplication, addition, etc. Everything but exponentiation works pretty well and I have no clue what could be causing problems in this one function. First of all I defined multiplication as:

void multip(const matrix& A, const matrix& B, matrix& result){
    int n = A.size();
    for (int i = 0; i<n; i++){
        for (int j = 0; j<n; j++){
            for (int k = 0; k< n; k++){
                result[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

and based on that I wanted to make a recursive (this is a must) exponentiation function as follows:

void expo(matrix& M, unsigned n){
    if (n>0){
        n--;
        multip(M, expo(M, n), M);}
    else{return;}
}

This does not work, returning [Error] Invalid use of void expression. I understood why this wouldn't work, but I have no clue how to get around that. Could somebody help me with that problem?

Upvotes: 1

Views: 3112

Answers (1)

Maxim Egorushkin
Maxim Egorushkin

Reputation: 136256

The main problem is that multip changes its 3rd argument, so it cannot be the same as the 1st, as in call multip(M, expo(M, n), M); in your code.

If you use function return values for returning values, as you should, it becomes straightforward.

Fixes and a working example:

#include <iostream>
#include <vector>

using namespace std;

typedef vector<double> vec;
typedef vector<vec> matrix;

matrix multip(const matrix& A, const matrix& B) {
    size_t n = A.size();
    matrix result(n, vec(n));
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n; ++j) {
            for (size_t k = 0; k < n; ++k) {
                result[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return result;
}

matrix expo(matrix const& M, unsigned n) {
    if(n < 1)
        throw;
    if(n == 1)
        return M;
    return multip(M, expo(M, n - 1));
}

void print(matrix const& M) {
    size_t n = M.size();
    for(size_t i = 0; i < n; ++i) {
        for(size_t j = 0; j < n; ++j)
            cout << M[i][j] << ' ';
        cout << '\n';
    }
}

int main() {
    matrix m(2, vec(2));
    m[0][0] = 2;
    m[1][1] = 2;
    print(m);
    cout << '\n';

    m = expo(m, 3);
    print(m);
    cout << '\n';
}

Outputs:

2 0 
0 2 

8 0 
0 8

Upvotes: 1

Related Questions