Page 32, Exercise 5 Multiplication
a. Counts
void mult(int a[][MAX_SIZE], int b[][MAX_SIZE], int c[][MAX_SIZE])
{
int i, j,k;
int count = 0;
for (i = 0; i < MAX_SIZE; i++) {
count ++; /*for i loop */
for (j = 0; j < MAX_SIZE; j++) {
c[i][j] = 0; count++; /* for assignment */
count++; /*for j loop */
for (k=0; k < MAX_SIZE; k++){
c[i][j] += (a[i][k] * b[k][j]); count++; /* for assignment */
count++; /* for k loop*/
}
count++; /*last time of k */
}
count++; /* last time of j */
}
count++; /* last time of i */
printf("Multiplication Count: %d\n", count);
}
b. Simplified Counts
void mult(int a[][MAX_SIZE], int b[][MAX_SIZE], int c[][MAX_SIZE])
{
int i, j,k;
int count = 0;
for (i = 0; i < MAX_SIZE; i++) {
for (j = 0; j < MAX_SIZE; j++) {
c[i][j] = 0;
count+=3; /* includes last time of k loop */
for (k=0; k < MAX_SIZE; k++){
c[i][j] += (a[i][k] * b[k][j]);
count+=2;
}
count+=2; /* for i loop and last time of j loop */
}
count++; /* last time of i */
printf("Multiplication Count: %d\n", count);
}
c. Final Count for 5x5 matrix: 336
d. Step Count Table
| Statement | s/e | f (MAX_S) = MAX_SIZE | Total Steps |
void mult(int a[][MAX_SIZE], int b[][MAX_SIZE],
int c[][MAX_SIZE])
{
int i, j,k;
for (i = 0; i < MAX_SIZE; i++)
for (j = 0; j < MAX_SIZE; j++)
{
c[i][j] = 0;
for (k=0; k < MAX_SIZE; k++)
c[i][j] += (a[i][k] * b[k][j]);
}
} |
0 0 0 0 1 1 0 1 1 1 0 0 |
1 1 1 1 MAX_S+1 MAX_S·MAX_S + MAX_S MAX_S·MAX_S MAX_S·MAX_S MAX_S·MAX_S·MAX_S + MAX_S·MAX_S·MAX_s MAX_S·MAX_S·MAX_S MAX_S·MAX_S MAX_S |
0 0 0 0 MAX_S+1 MAX_S·MAX_S + MAX_S 0 MAX_S·MAX_S MAX_S·MAX_S·MAX_S + MAX_S·MAX_S·MAX_S MAX_S·MAX_S·MAX_S 0 0 |
| Total : 3·MAX_SIZE3 + 2·MAX_SIZE2 + 2·MAX_SIZE + 1 = O(MAX_SIZE)3 | |||