troubleshooting Question

From what I understand, Strassen's method for multiplying Matrices should be the fastest... but the Divide & Conquer method is clearly the fastest in my testing... Am I doing something wrong? Or is this correct?

The instructions were: "The total time spent is then divided by the number of times the algorithm is performed to obtain the time taken to solve the given instance"

So I just have an individual "counter++" in every method and divide the time "recorded time/ counter++".. (hopefully this is correct)

So far here are my times: (in order top/down: classic, divide & conquer, strassen) (size = size of matrix)

size 2

Time Elapsed:8660 nano-seconds

Time Elapsed:3849 nano-seconds

Time Elapsed:5377 nano-seconds

size 4

Time Elapsed:24864 nano-seconds

Time Elapsed:3080 nano-seconds

Time Elapsed:5229 nano-seconds

size 8

Time Elapsed:125435 nano-seconds

Time Elapsed:2920 nano-seconds

Time Elapsed:5196 nano-seconds

size 16

Time Elapsed:867149 nano-seconds

Time Elapsed:1559 nano-seconds

Time Elapsed:2853 nano-seconds

size 32

Time Elapsed:5191721 nano-seconds

Time Elapsed:972 nano-seconds

Time Elapsed:1722 nano-seconds

size 64

Time Elapsed:8155785 nano-seconds

Time Elapsed:874 nano-seconds

Time Elapsed:1696 nano-seconds

Example of how I'm testing the time:

DIVIDE & CONQUER CODE

SAMPLE OUTPUT I promise I did. Here's an example of my output for a matrix of size 4:

1st Random Generated Matrix: 10 57 33 70

6 12 38 70

20 41 65 98

83 0 31 73

2nd Random Generated Matrix: 11 70 54 79

2 51 38 71

27 53 37 86

48 87 20 41

Classic Multiplication Matrix: 4475 11446 5327 10545

4476 9136 3586 7464

6761 15462 7003 14099

5254 13804 7089 12216

Time Elapsed:21232 nano-seconds

Divide and Conquer Multiplication Matrix: 4475 11446 5327 10545

4476 9136 3586 7464

6761 15462 7003 14099

5254 13804 7089 12216

Time Elapsed:3042 nano-seconds

Strassen Multiplication Matrix: 4475 11446 5327 10545

4476 9136 3586 7464

6761 15462 7003 14099

5254 13804 7089 12216

Time Elapsed:5303 nano-seconds

The instructions were: "The total time spent is then divided by the number of times the algorithm is performed to obtain the time taken to solve the given instance"

So I just have an individual "counter++" in every method and divide the time "recorded time/ counter++".. (hopefully this is correct)

So far here are my times: (in order top/down: classic, divide & conquer, strassen) (size = size of matrix)

size 2

Time Elapsed:8660 nano-seconds

Time Elapsed:3849 nano-seconds

Time Elapsed:5377 nano-seconds

size 4

Time Elapsed:24864 nano-seconds

Time Elapsed:3080 nano-seconds

Time Elapsed:5229 nano-seconds

size 8

Time Elapsed:125435 nano-seconds

Time Elapsed:2920 nano-seconds

Time Elapsed:5196 nano-seconds

size 16

Time Elapsed:867149 nano-seconds

Time Elapsed:1559 nano-seconds

Time Elapsed:2853 nano-seconds

size 32

Time Elapsed:5191721 nano-seconds

Time Elapsed:972 nano-seconds

Time Elapsed:1722 nano-seconds

size 64

Time Elapsed:8155785 nano-seconds

Time Elapsed:874 nano-seconds

Time Elapsed:1696 nano-seconds

Example of how I'm testing the time:

```
System.out.println("\nStrassen Multiplication Matrix:");
startTime = System.nanoTime();
temp = m.strassen(m.m1, m.m2);
endTime = System.nanoTime();
m.print(temp);
System.out.println("Time Elapsed:" + (endTime - startTime)/m.count_strassen + " nano-seconds");
```

DIVIDE & CONQUER CODE

```
if (n == 1) {
result[0][0] = a[0][0] * b[0][0];
}
else {
int[][] a11 = new int[n/2][n/2];
int[][] a12 = new int[n/2][n/2];
int[][] a21 = new int[n/2][n/2];
int[][] a22 = new int[n/2][n/2];
int[][] b11 = new int[n/2][n/2];
int[][] b12 = new int[n/2][n/2];
int[][] b21 = new int[n/2][n/2];
int[][] b22 = new int[n/2][n/2];
initialize(a, a11, 0 , 0);
initialize(a, a12, 0 , n/2);
initialize(a, a21, n/2, 0);
initialize(a, a22, n/2, n/2);
initialize(b, b11, 0 , 0);
initialize(b, b12, 0 , n/2);
initialize(b, b21, n/2, 0);
initialize(b, b22, n/2, n/2);
int[][] c11 = add(divideandconq(a11, b11), divideandconq(a12, b21));
int[][] c12 = add(divideandconq(a11, b12), divideandconq(a12, b22));
int[][] c21 = add(divideandconq(a21, b11), divideandconq(a22, b21));
int[][] c22 = add(divideandconq(a21, b12), divideandconq(a22, b22));
putTogether(c11, result, 0 , 0);
putTogether(c12, result, 0 , n/2);
putTogether(c21, result, n/2, 0);
putTogether(c22, result, n/2, n/2);
}
return result;
```

```
if (n == 1) {
result[0][0] = a[0][0] * b[0][0];
}
else {
int[][] a11 = new int[n/2][n/2];
int[][] a12 = new int[n/2][n/2];
int[][] a21 = new int[n/2][n/2];
int[][] a22 = new int[n/2][n/2];
int[][] b11 = new int[n/2][n/2];
int[][] b12 = new int[n/2][n/2];
int[][] b21 = new int[n/2][n/2];
int[][] b22 = new int[n/2][n/2];
initialize(a, a11, 0 , 0);
initialize(a, a12, 0 , n/2);
initialize(a, a21, n/2, 0);
initialize(a, a22, n/2, n/2);
initialize(b, b11, 0 , 0);
initialize(b, b12, 0 , n/2);
initialize(b, b21, n/2, 0);
initialize(b, b22, n/2, n/2);
int[][] _m1 = strassen(add(a11, a22), add(b11, b22));
int[][] _m2 = strassen(add(a21, a22), b11);
int[][] _m3 = strassen(a11, minus(b12, b22));
int[][] _m4 = strassen(a22, minus(b21, b11));
int[][] _m5 = strassen(add(a11, a12), b22);
int[][] _m6 = strassen(minus(a21, a11), add(b11, b12));
int[][] _m7 = strassen(minus(a12, a22), add(b21, b22));
int[][] c11 = add(minus(add(_m1, _m4), _m5), _m7);
int[][] c12 = add(_m3, _m5);
int[][] c21 = add(_m2, _m4);
int[][] c22 = add(minus(add(_m1, _m3), _m2), _m6);
putTogether(c11, result, 0 , 0);
putTogether(c12, result, 0 , n/2);
putTogether(c21, result, n/2, 0);
putTogether(c22, result, n/2, n/2);
}
return result;
```

SAMPLE OUTPUT I promise I did. Here's an example of my output for a matrix of size 4:

1st Random Generated Matrix: 10 57 33 70

6 12 38 70

20 41 65 98

83 0 31 73

2nd Random Generated Matrix: 11 70 54 79

2 51 38 71

27 53 37 86

48 87 20 41

Classic Multiplication Matrix: 4475 11446 5327 10545

4476 9136 3586 7464

6761 15462 7003 14099

5254 13804 7089 12216

Time Elapsed:21232 nano-seconds

Divide and Conquer Multiplication Matrix: 4475 11446 5327 10545

4476 9136 3586 7464

6761 15462 7003 14099

5254 13804 7089 12216

Time Elapsed:3042 nano-seconds

Strassen Multiplication Matrix: 4475 11446 5327 10545

4476 9136 3586 7464

6761 15462 7003 14099

5254 13804 7089 12216

Time Elapsed:5303 nano-seconds

Join the community to see this answer!

Join our exclusive community to see this answer & millions of others.

Unlock 2 Answers and 55 Comments.

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert

See if this solution works for you by signing up for a 7 day free trial.

Unlock 2 Answers and 55 Comments.

Try for 7 days”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.