|
|
This program was written by a friend of mine while we were both at college. The homework assignment was to write a matrix-multiply routine. However, the function itself had to be written in assembly language. In order to make it run as fast as possible, he used an algorithm that I designed, which vectorized the matrix.
In order to test the system, he wrote a short test function in SAIL [2]. When we tested the program, we got the wrong answers. Both of us poured over every line of that code from 8:00 p.m. until 2:00 a.m. the next morning. When we finally found the error, we both burst out laughing because it was such a silly mistake.
The program below is a simplified version of that famous code. It's written entirely in one language (C) and uses a much simpler multiplication algorithm. But the original bug still remains. What's going on?
1 /**************************************************
2 * matrix-test -- Test matrix multiply *
3 **************************************************/
4 #include <stdio.h>
5
6 /**************************************************
7 * matrix_multiply -- Multiple two matrixes *
8 **************************************************/
9 static void matrix_multiply(
10 int result[3][3], /* The result */
11 int matrixl[3][3],/* One multiplicand */
12 int matrix2[3][3] /* The other multiplicand */
13 )
14 {
15 /* Index into the elements of the matrix */
16 int row, col, element;
17
18 for(row = 0; row < 3; ++row)
19 {
20 for(col = 0; col < 3; ++col)
21 {
22 result[row][col] = 0;
23 for(element = 0; element < 3; ++element)
24 {
25 result[row][col] +=
26 matrix1[row][element] *
27 matrix2[element][col];
28 }
29 }
32 }
33 }
34
35 /************************************************
36 * matrix_print -- Output the matrix *
37 ************************************************/
38 static void matrix_print(
39 int matrix[3][3] /* The matrix to print */
40 )
41 {
42 int row, col; /* Index into the matrix */
43
44 for (row = 0; row < 3; ++row)
45 {
46 for (col = 0; col < 3; ++col)
47 {
48 printf("%o\t", matrix[row][col]);
49 }
50 printf("\n");
51 }
52 }
53
54 int main(void)
55 {
56 /* One matrix for multiplication */
57 int matrix_a[3][3] = {
58 {45, 82, 26},
59 {32, 11, 13},
60 {89, 81, 25}
61 };
62 /* Another matrix for multiplication */
63 int matrix_b[3][3] = {
64 {32, 43, 50},
65 {33, 40, 52},
66 {20, 12, 32}
67 };
68 /* Place to put result */
69 int result[3][3];
70
71 matrix_multiply(result, matrix_a, matrix_b);
72 matrix_print(result);
73 return (o);
74 }
75
[2]SAIL was an old system programming language for the PDP-10. The debugger was called BAIL. Later a machine independent version of the language was created called MAIN SAIL. It pre-dated C by several years.
|
|