//Hello, I\'m suppose to write a code that empirically compares the performance
ID: 2246605 • Letter: #
Question
//Hello, I'm suppose to write a code that empirically compares the performance of a naive and a fast two by two matrix exponentiation method defining a class Mat2By2 that implements the interface called Mat2By2API as shown with the output sample and program demonstrating on how it should run.
Output Example:
Enter the top-left, top-right, bottom-left and bottom-right entries of the first matrix:
52 45 87 95
Enter the top-left, top-right, bottom-left and bottom-right entries of the second matrix: 452 789 654 123
m1 = [[52, 45], [87, 95]]
m2 = [[452, 789], [654, 123]]
m1 = [[52, 45], [87, 95]]
m2 = [[452, 789], [654, 123]]
(m1 - m2)(m1 + m2) = ........
|(m1 - m2)(m1 + m2)| = ........
Please input a Fibonnacci number? 250
Fib(250) = ........
Empirical Analysis of Naive vs Fast Matrix Exponentiation in Generating 19 Terms of the Fibonacci Sequence
=========================================================
Term Naive Time(10^-6s) Fast Time(10^-6s)
----------------------------------------------------------
1000 ........ ........
1500 ........ ........
2000 ........ ........
2500 ........ ........
3000 ........ ........
3500 ........ ........
4000 ........ ........
4500 ........ ........
5000 ........ ........
5500 ........ ........
6000 ........ ........
6500 ........ ........
7000 ........ ........
7500 ........ ........
8000 ........ ........
8500 ........ ........
9000 ........ ........
9500 ........ ........
10000 ........ ........
----------------------------------------------
//Also, here is my current progress on this program. Comments on certain parts of the program is appreciated. Thanks. :)
Mat2By2API.java
import java.math.BigInteger;
public interface Mat2By2API
{
BigInteger[][] fastPower(BigInteger m[][], int n);
}
Mat2By2.java
import java.math.BigInteger;
public class Mat2By2 implements Mat2By2API{
public static void printMatrix(BigInteger[][] m){
for(int i=0; i
for(int j=0; j
System.out.print(m[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args){
BigInteger matrix [][] = {
{BigInteger.valueOf(1), BigInteger.valueOf(2), BigInteger.valueOf(3)},
{BigInteger.valueOf(4), BigInteger.valueOf(5), BigInteger.valueOf(6)},
{BigInteger.valueOf(7), BigInteger.valueOf(8), BigInteger.valueOf(9)},
};
Mat2By2API api = new Mat2By2();
System.out.println("Original Matrix: ");
printMatrix(matrix);
System.out.println("Result Matrix: ");
printMatrix(api.fastPower(matrix, 2));
}
@Override
public BigInteger[][] fastPower(BigInteger[][] m, int n){
if(n < 1){
return null;
}
if(n == 1){
return m;
}
BigInteger[][] result = new BigInteger[m.length][m.length];
// identity matrix creation
for (int i = 0; i < m.length; i++)
{
for (int j = 0; j < m.length; j++){
result[i][j] = BigInteger.ZERO;
if(i==j){
result[i][j] = BigInteger.ONE;
}
}
}
while(n != 0){
if(n%2!=0){
result = multiply(result, m);
}
n = n/2;
if(n != 0){
m = multiply(m,m);
}
}
return result;
}
public BigInteger[][] multiply(BigInteger[][] m, BigInteger[][] n) {
BigInteger[][] result = new BigInteger[m.length][m.length];
for (int i = 0; i < m.length; i++)
{
for (int j= 0; j < m.length; j++)
{
result[i][j] = BigInteger.ZERO;
for (int k = 0; k < m.length; k++)
{
result[i][j] = m[i][k].multiply(n[k][j]).add(result[i][j]);
}
}
}
return result;
}
}
Explanation / Answer
Hi..Below code looks good
Mat2By2API.java
import java.math.BigInteger;
public interface Mat2By2API
{
BigInteger[][] fastPower(BigInteger m[][], int n);
}
Mat2By2.java
import java.math.BigInteger;
public class Mat2By2 implements Mat2By2API{
public static void Prints the matrix(BigInteger[][] m){
for(int i=0; i
for(int j=0; j
System.out.print(m[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args){
BigInteger matrix [][] = {
{BigInteger.valueOf(1), BigInteger.valueOf(2), BigInteger.valueOf(3)},
{BigInteger.valueOf(4), BigInteger.valueOf(5), BigInteger.valueOf(6)},
{BigInteger.valueOf(7), BigInteger.valueOf(8), BigInteger.valueOf(9)},
};
Mat2By2API api = new Mat2By2();
System.out.println("Original Matrix: ");
Prints the matrix(matrix);
System.out.println("Result Matrix: ");
Prints the matrix(api.fastPower(matrix, 2));
}
@Override
public BigInteger[][] fastPower(BigInteger[][] m, int n){
if(n < 1){
return null;
}
if(n == 1){
return m;
}
BigInteger[][] result = new BigInteger[m.length][m.length];
// identity matrix creation
for (int i = 0; i < m.length; i++)
{
for (int j = 0; j < m.length; j++){
result[i][j] = BigInteger.ZERO;
if(i==j){
result[i][j] = BigInteger.ONE;
}
}
}
while(n != 0){
if(n%2!=0){
result = Multiplies(result, m);
}
n = n/2;
if(n != 0){
m = Multiplies(m,m);
}
}
return result;
}
public BigInteger[][] Multiplies(BigInteger[][] m, BigInteger[][] n) {
BigInteger[][] result = new BigInteger[m.length][m.length];
for (int i = 0; i < m.length; i++)
{
for (int j= 0; j < m.length; j++)
{
result[i][j] = BigInteger.ZERO;
for (int k = 0; k < m.length; k++)
{
result[i][j] = m[i][k].Multiplies(n[k][j]).add(result[i][j]);
}
}
}
return result;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.