BUGFIX-66

Bug 46: Winograd Done Bad

Winograd's algorithm for matrix multiplication roughly halves the number of scalar multiplications.
This code multiplies two input matrices (mk times kn) and adds the result to a third input matrix (mn).
Row-major: mk has m rows and k columns, kn has k rows and n columns, mn has m rows and n columns.
Winograd multiplies a pair of row elements with a pair of column elements using 1 scalar multiplication.
The trick: (row1 * col1) + (row2 * col2) = (row1 + col2) * (row2 + col1) - (row1 * row2) - (col1 * col2)
For each mk row, it prepares a sum of (row1 * row2) for disjoint pairs of consecutive scalars row1, row2.
For each kn column, it prepares a sum of (col1 * col2) for disjoint pairs of consecutive scalars col1, col2.
These prepared sums are reused many times, as each row of mk is multiplied with every column of kn.

Fix The Tiny Bug In This Go Code:

func winograd(m, n, k int, mk, kn, mn []float32) { var ( w1 = make([]float32, m) w2 = make([]float32, n) ) for i1 := range w1 { var ( sum = float32(0) i3 = i1 * k last = i3 + k - 1 ) for ; i3 < last; i3 += 2 { sum -= mk[i3] * mk[i3+1] } w1[i1] = sum } for i2 := range w2 { var ( sum = float32(0) i4 = i2 last = len(kn) - n ) for ; i4 < last; i4 += 2 * n { sum -= kn[i4] * kn[i4+n] } w2[i2] = sum } for i1, w1 := range w1 { for i2, w2 := range w2 { var ( sum = w1 + w2 i3 = i1 * k last = i3 + k - 1 i4 = i2 ) for ; i3 < last; i3 += 2 { var ( x = mk[i3] + kn[i4+1] y = mk[i3+1] + kn[i4] ) sum += x * y i4 += 2 * n } if i3 == last { sum += mk[i3] * kn[i4] } mn[i1*n+i2] += sum } } }

To receive a hint, submit unfixed code.