CODEWITHSUNDEEP
carraysmatrix
Ardembly
Ardembly

Reputation: 233

Raising a 2D array to a power in C

I'm using C and have a 2D array representing a square matrix. What I want to do is to calculate the matrix to the power of n, a given integer.

I'm after the most efficient way to do this. My first thought was to multiply the matrix to itself n times but then I heard of exponentiation by squaring. However I'm not sure how to implement this, could someone please guide me through it?

Upvotes: 0

Views: 1103

Answers (1)

samgak
samgak

Reputation: 24417

Here is the basic outline:

Matrix matrixExponent(Matrix m, int n)
{
      Matrix accumulator = MatrixIdentity();
      Matrix power2 = m;

      while(n != 0)
      {
           if(n & 1)
                 accumulator = MatrixMultiply(&accumulator, &power2);
           power2 = MatrixMultiply(&power2, &power2);
           n = n / 2;
      }
      return accumulator;
}

You store an accumulator, which is the partially computed exponent. A given integer exponent can be broken down into a series of power-of-2 exponents multiplied together. For example when raising an array to the power of 14 (1110 in binary), the matrix multiplied by itself 14 times is equal to:

m14 = m8 * m4 * m2

So you just compute all the powers of two by repeatedly multiplying power2 with itself, while stepping through each bit of the integer exponent n, and multiplying power2 with the accumulator each time the bit is a 1.

Upvotes: 4

Related Questions