Skip to content

Added MatrixFastPower.java #501

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
varunu28 merged 2 commits into from
Aug 30, 2018
Merged

Added MatrixFastPower.java #501

Changes from 1 commit
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
f713a5f
Added MatrixFastPower.java
DDullahan Aug 30, 2018
55c179b
Added MatrixFastPower.java with changes
DDullahan Aug 30, 2018
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Added MatrixFastPower.java with changes
  • Loading branch information
@DDullahan
DDullahan committed Aug 30, 2018
commit 55c179bf19ddcb1c3fcf5e1d6ec56ff6a1788309
112 changes: 82 additions & 30 deletions DataStructures/Matrix/MatrixFastPower.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,5 +1,3 @@
import java.util.*;

/**
*
* Java implementation of Matrix fast power
Expand All @@ -14,11 +12,67 @@
* other Matrix basic operator is based on @author Kyler Smith, 2017
*
* @author DDullahan, 2018
*
*
*/

class MatrixFastPower {

/**
* Matrix Fast Power
*
* @param matrix : square Matrix
* @param k : power of Matrix
* @return product
*/
public static Matrix FastPower(Matrix matrix, int k) throws RuntimeException {

if(matrix.getColumns() != matrix.getRows())
throw new RuntimeException("Matrix is not square Matrix.");

int[][] newData = new int[matrix.getColumns()][matrix.getRows()];

for(int i = 0; i < matrix.getColumns(); i++)
newData[i][i] = 1;

Matrix newMatrix = new Matrix(newData),
coMatrix = new Matrix(matrix.data);

while(k != 0) {

if((k & 1) != 0)
newMatrix = newMatrix.multiply(coMatrix);

k >>= 1;
coMatrix = coMatrix.multiply(coMatrix);

}

return newMatrix;
}

public static void main(String[] argv) {

int[][] data = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
Matrix matrix = new Matrix(data);

System.out.println("original matrix : ");
System.out.println(matrix.toString());

matrix = MatrixFastPower.FastPower(matrix, 5);

System.out.println("after power : ");
System.out.println(matrix.toString());

matrix = MatrixFastPower.FastPower(matrix, 1000000);

System.out.println("notice, large power may cause overflow : ");
System.out.print(matrix.toString());
System.out.println("you can use mod to fix that :-) ");

}
}
class Matrix {
private int[][] data;
public int[][] data;

/**
* Constructor for the matrix takes in a 2D array
Expand Down Expand Up @@ -106,34 +160,32 @@ public Matrix multiply(Matrix other) throws RuntimeException {
}

/**
* Matrix Fast Power
*
* @param k : power of Matrix
* @return product
*/
public Matrix MatrixFastPower(int k) throws RuntimeException {

if(this.getColumns() != this.getRows())
throw new RuntimeException("Matrix is not square Matrix.");

int[][] newData = new int[this.getColumns()][this.getRows()];

for(int i = 0; i < this.getColumns(); i++)
newData[i][i] = 1;

Matrix newMatrix = new Matrix(newData),
coMatrix = new Matrix(this.data);

while(k != 0) {

if((k & 1) != 0)
newMatrix = newMatrix.multiply(coMatrix);

k >>= 1;
coMatrix = coMatrix.multiply(coMatrix);
* Returns the Matrix as a String in the following format
*
* [ a b c ] ...
* [ x y z ] ...
* [ i j k ] ...
* ...
*
* @return Matrix as String
* TODO: Work formatting for different digit sizes
*/
public String toString() {
String str = "";

for(int i = 0; i < this.data.length; i++) {
str += "[ ";

for(int j = 0; j < this.data[0].length; j++) {
str += data[i][j];
str += " ";
}

str += "]";
str += "\n";
}

return newMatrix;
return str;
}

}