So my fast time is still slower than my naive time.. can someone please check my code and tell me where I went wrong.. I can't seem to find the issue. Thanks!!

It's related to this question that has a little bit more info on it:

https://www.chegg.com/homework-help/questions-and-answers/fastpower-naivepower-naivepower-supposed-run-slower-fastpower-fastpower-actually-running-s-q23571134

***************************

MatrixExponentialDemo

***************************

/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package mat2by2;

import java.math.BigInteger; import java.util.*;

/** * * @author Mousefire */ public class MatrixExponentiationDemo extends Mat2by2 {

public static void main(String[] args) { Scanner input = new Scanner(System.in);

/* Gets input for first matrix and declares variables */ System.out.println("Enter the top-left, top-right, bottom left, and bottom-right entries of the first matrix:"); BigInteger tL = input.nextBigInteger(); BigInteger tR = input.nextBigInteger(); BigInteger bL = input.nextBigInteger(); BigInteger bR = input.nextBigInteger();

Mat2by2 mat1 = new Mat2by2(tL, tR, bL, bR);//creates the firt matrix

/* Gets input for second matrix */ System.out.println("Enter the top-left, top-right, bottom left, and bottom-right entries of the second matrix:");

tL = input.nextBigInteger(); tR = input.nextBigInteger(); bL = input.nextBigInteger(); bR = input.nextBigInteger(); Mat2by2 mat2 = new Mat2by2(tL, tR, bL, bR);//creates the second matrix

/* Outputs the matrixes that were input to the System */ System.out.println("m1 = " + mat1.toString()); System.out.println("m2 = " + mat2.toString());

/* subtraction and addition of matrixes currently does nothing lol */ Mat2by2 matANS =(((mat1.subtract(mat2))).multiply((mat1.add(mat2)))); System.out.println("(m1 - m2)(m1 + m2) = " + matANS); System.out.println("|(m1 - m2)(m1 + m2)| = " + matANS.determinant());// determinant(mat1) /* Fibonacci computing */ System.out.println("Which Fibonacci number do you wish to compute?"); int n = input.nextInt(); System.out.println("Fib("+n+") = "); System.out.println(" "+naivePower(matANS,n));//working System.out.println(" "+fastPower(matANS,n)); // prints out the top of the chart that titles the Fibonacci Sequence of both the Naive and Fast Time //********************** System.out.println(" Empirical Analysis of naive vs. Fast Matrix Exponentiation in Generating 19 Terms of the Fibonacci Sequence. "); System.out.println("============================================================"); System.out.println("Term\t\tNaive Time(10^-6s)\tFast Time(10^-6s)"); System.out.println("------------------------------------------------------------");

// assigns the integer to 1000 as the start of the empirical analysis instructed in the assignment n = 1000;

long fast_time, naive_time, naiveTime, fastTime; // lets the empirical analysis run until it reaches 10000. while(n <= 10000){ // the naive method time starts naive_time = System.nanoTime();

naivePower(matANS, n); naiveTime = System.nanoTime(); // the fast power method time starts fast_time = System.nanoTime(); fastPower(matANS,n);

fastTime = System.nanoTime() ; naive_time = (naiveTime - naive_time)/1000; fast_time = (fastTime - fast_time)/1000; System.out.println(n+"\t\t"+naive_time+"\t\t\t"+fast_time); n += 500; } System.out.println("------------------------------------------------------------"); }

/** * Computes the power of the specified matrix by successive squaring * @param m a 2x2 matrix of BigInteger objects * @param n a positive integer representing the exponent * @return the nth power of the specified matrix (m^n) * @throws IllegalArgumentException when n <= 0 */ private static Mat2by2 fastPower(Mat2by2 m, int n){ Mat2by2 result = new Mat2by2(BigInteger.ONE,BigInteger.ZERO,BigInteger.ZERO,BigInteger.ONE); while (n!=0){ if(n%2 != 0){ result = result.multiply(m); } n = n/2; if(n!=0){ m = m.multiply(m); } } return result; } /** 2 * Computes the power of the specified matrix by performing n-1 3 * multiplications when the power is n 4 * @param m a 2x2 matrix of BigInteger objects 5 * @param n a positive integer representing the exponent 6 * @return the power of the specified matrix (m^n) 7 * @throws IllegalArgumentException when n <= 0 8 */ private static Mat2by2 naivePower(Mat2by2 m, int n){ Mat2by2 result = new Mat2by2(BigInteger.ONE,BigInteger.ZERO,BigInteger.ZERO,BigInteger.ONE); for(int i=0; i result = m.multiply(m); } return result; } }

**********************

Mat2by2

******************

/** * To * CSC 3102 Homework Assignment # 1 * * @author Vanessa Hoffmann * @since 8/29/17 * @see Mat2By2API.java */ package mat2by2;

import java.math.BigInteger;

/** * * @author Mousefire */ public class Mat2by2 {

BigInteger entries[][] = new BigInteger[2][2]; /* Creates a constructor that creates a two d array all set to zero */ public Mat2by2() { this.entries[0][0] = BigInteger.ZERO; this.entries[0][1] = BigInteger.ZERO; this.entries[1][0] = BigInteger.ZERO;; this.entries[1][1] = BigInteger.ZERO; }

/* Creates a constructor that creates a two d array with given values */ public Mat2by2(BigInteger topLeft, BigInteger topRight, BigInteger botLeft, BigInteger botRight) {

this.entries[0][0] = topLeft; this.entries[0][1] = topRight; this.entries[1][0] = botLeft; this.entries[1][1] = botRight;

}

public Mat2by2 add(Mat2by2 augend) { Mat2by2 added = new Mat2by2(); added.entries[0][0] = getTopLeft().add(augend.getTopLeft()); added.entries[0][1] = getTopRight().add(augend.getTopRight()); added.entries[1][0] = getBottomLeft().add(augend.getBottomLeft()); added.entries[1][1] = getBottomRight().add(augend.getBottomRight()); return added; }

public Mat2by2 subtract(Mat2by2 subtrahend) { Mat2by2 subtract = new Mat2by2(); subtract.entries[0][0] = getTopLeft().subtract(subtrahend.getTopLeft()); subtract.entries[0][1] = getTopRight().subtract(subtrahend.getTopRight()); subtract.entries[1][0] = getBottomLeft().subtract(subtrahend.getBottomLeft()); subtract.entries[1][1] = getBottomRight().subtract(subtrahend.getBottomRight()); return subtract; } public Mat2by2 multiply(Mat2by2 multiplier) { Mat2by2 multi = new Mat2by2(); multi.entries[0][0] = (getTopLeft().multiply(multiplier.getTopLeft())).add((getTopRight().multiply(multiplier.getBottomLeft()))); multi.entries[0][1] = (getTopLeft() .multiply(multiplier.getTopRight())).add(getTopRight().multiply(multiplier.getBottomRight())); multi.entries[1][0] = (getBottomLeft().multiply(multiplier.getTopLeft())).add(getBottomRight().multiply(multiplier.getBottomLeft())); multi.entries[1][1] = (getBottomLeft().multiply(multiplier.getTopRight())).add(getBottomRight().multiply(multiplier.getBottomRight())); return multi; /* topLeft.multiply(m.topLeft)).add(topRight.multiply(m.bottomLeft)) , (topLeft.multiply(m.topRight)).add(topRight.multiply(m.bottomRight)) , (bottomLeft.multiply(m.topLeft)).add(bottomRight.multiply(m.bottomLeft)), (bottomLeft.multiply(m.topRight)).add(bottomRight.multiply(m.bottomRight))); */ }

public BigInteger determinant() { return (getTopLeft().multiply(getBottomRight())).subtract(getBottomLeft().multiply(getTopRight())); }

public BigInteger getTopLeft() { return entries[0][0]; }

public BigInteger getTopRight() { return entries[0][1]; }

public BigInteger getBottomLeft() { return entries[1][0]; }

public BigInteger getBottomRight() { return entries[1][1]; }

public String toString() { return ("[[" + getTopLeft() + ", " + getTopRight() + "], [" + getBottomLeft() + ", " + getBottomRight() + "]]");

}

}

***************************

Output

***************************

Enter the top-left, top-right, bottom left, and bottom-right entries of the first matrix:

55

22

33

66

Enter the top-left, top-right, bottom left, and bottom-right entries of the second matrix:

44

77

55

66

m1 = [[55, 22], [33, 66]]

m2 = [[44, 77], [55, 66]]

(m1 - m2)(m1 + m2) = [[-3751, -6171], [-2178, -2178]]

|(m1 - m2)(m1 + m2)| = -5270760

Which Fibonacci number do you wish to compute?

5

Fib(5) =

[[27510439, 36587859], [12913362, 18184122]]

[[-8252415739637800951, -11227313322985924131], [-3962581172818561458, -5390551559268839898]]

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 3511 9803

1500 1314 3086

2000 2049 2613

2500 2095 5722

3000 2033 6348

3500 2176 5186

4000 2361 4340

4500 2826 6360

5000 3245 7103

5500 3529 8599

6000 3725 8541

6500 4171 7753

7000 2551 6424

7500 2830 6984

8000 3121 7746

8500 2942 11002

9000 3023 11292

9500 3194 11710

10000 3511 14865

------------------------------------------------------------