# Help with Fast Matrix Exponentiation

• September 18th, 2012, 12:09 PM
asundar
Help with Fast Matrix Exponentiation
hey everyone,

I feel like I am close to the answer, but I'm just missing something little. What I'm supposed to do, basically, is come up with a program that allows me to increase matrices exponentially. My problem lies when I want to do anything higher than a power of two. For example, when I raise it to the power of 3, it does it by 4 instead. If I do it by 4, it does it by 6. Can anyone help me? I feel like it's something small that I am overlooking, but I am not able to figure it out.

Code :

import java.io.*;
import java.util.Scanner;
public class Matrix {
static int[][] mult(int[][] X, int[][] Y) {
int Z[][] = new int[2][2];
Z[0][0] = X[0][0]*Y[0][0] + X[0][1]*Y[1][0];
Z[0][1] = X[0][0]*Y[0][1] + X[0][1]*Y[1][1];
Z[1][0] = X[1][0]*Y[0][0] + X[1][1]*Y[0][1];
Z[1][1] = X[1][0]*Y[1][0] + X[1][1]*Y[1][1];
return Z;
}
public static void main(String argv[]) {
// create a scanner for interactive input
Scanner scin = new Scanner(System.in);
int matrix[][] = new int[2][2];
int B[][] = new int[2][2];
int A[][] = new int[2][2];
int k,n;
System.out.print("[ M[0][0] M[0][1] ] =  ");
matrix[0][0] = scin.nextInt(); matrix[0][1] = scin.nextInt();
System.out.print("[ M[1][0] M[1][1] ] =  ");
matrix[1][0] = scin.nextInt(); matrix[1][1] = scin.nextInt();
System.out.print("n =  ");
n = scin.nextInt();
k = n; B = matrix;
if ((k==1))
{
A = matrix;
}
else
{
int m=1;
int C[][]=matrix;
C[0][0]=1;C[0][1]=2;
C[1][0]=3;C[1][1]=4;
while(m<n)
{
if(m==n)
{
break;
}
m++;

A[0][0] = (C[0][0]*matrix[0][0])+(C[1][0]*matrix[0][1]); A[0][1] = (C[0][0]*matrix[0][1])+(C[0][1]*matrix[1][1]);
A[1][0] = (C[1][0]*matrix[0][0])+(C[1][1]*matrix[1][0]); A[1][1] = (C[1][0]*matrix[0][1])+(C[1][1]*matrix[1][1]);

C[0][0]=A[0][0];C[0][1]=A[0][1];
C[1][0]=A[1][0];C[1][1]=A[1][1];

}
}
while(k > 0)
{
B= mult(B,B);
if ((k%1) == 1) A = mult(A,B);
k = k/2;
}
System.out.println( A[0][0] + "  " + A[0][1]);
System.out.println( A[1][0] + "  " + A[1][1]);
}
}

• September 18th, 2012, 01:01 PM
Norm
Re: Help with Fast Matrix Exponentiation
Can you post the program's output, explain what is wrong with it and show what the output should be?

Also please post pseudo code (or a detailed description) for the algorithm that the code is supposed to be following.

NOTE: This code has a poor coding style: putting multiple statements on the same line.
• September 18th, 2012, 02:41 PM
asundar
Re: Help with Fast Matrix Exponentiation
Ignore this, I found out what had happened from someone in my class about two hours later. Sorry for prematurely posting.