# 2017q1 Homework5 (matrix)
constributed by <`henry0929016816`>
>請注意程式碼排版
>[name=課程助教][color=red]
>感謝助教的提醒，貼 code 的時候亂掉了，沒有注意到
>[name=henry0929016816][color=blue]
## 原本 naive 版 matrix 的缺點
* 只能實作 4x4 的矩陣
不能實作其他大小的矩陣，由於 `assign` 、 `equal` 、 `mul` 函式都已經寫好 `row` 跟 `col` 的大小了，就是 ==4== 所以如果使用者傳入不是 4x4 的矩陣出來的結果可能不如預期。
* `matrix_naive.c` ==assign==
```c=
static void assign(Matrix *thiz, Mat4x4 data)
{
/* FIXME: don't hardcode row & col */
thiz->row = thiz->col = 4;
thiz->priv = malloc(4 * 4 * sizeof(float));
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
PRIV(thiz)->values[i][j] = data.values[i][j];
}
```
* `matrix_naive.c` ==equal==
```c=
static bool equal(const Matrix *l, const Matrix *r)
{
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (PRIV(l)->values[i][j] + epsilon < PRIV(r)->values[i][j] ||
PRIV(r)->values[i][j] + epsilon < PRIV(l)->values[i][j])
return false;
return true;
}
```
* `matrix_naive.c` ==mul==
```c=
bool mul(Matrix *dst, const Matrix *l, const Matrix *r)
{
/* FIXME: error hanlding */
dst->priv = malloc(4 * 4 * sizeof(float));
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
for (int k = 0; k < 4; k++)
PRIV(dst)->values[i][j] += PRIV(l)->values[i][k] *
PRIV(r)->values[k][j];
return true;
}
```
* 物件的實作還不夠直覺
原本的程式，如果要對 Matrix 型態的物件進行操作，必須創造 MatrixAlgo 的物件提供相關函式，才能進行對應的操作，這樣很不直覺，如果每個 Matrix 物件本身就擁有相對應的操作函式，我們就不需要多餘的建立 MatrixAlgo。
* `test-matrix.c`
```c=
int main()
{
MatrixAlgo *algo = matrix_providers[0];
Matrix dst, m, n, fixed;
algo->assign(&m, (Mat4x4) {
.values = {
{ 1, 2, 3, 4, },
{ 5, 6, 7, 8, },
{ 1, 2, 3, 4, },
{ 5, 6, 7, 8, },
},
});
}
```
## 將原版函式擴充成能實作 nxm 的矩陣
* 新增 data 到 Matrix 的資料結構
`matrix_expansion.h`
```c=
typedef struct _Matrix {
...
...
float **data;
} Matrix;
```
* 新增 create 函式，能建立任意 col 跟 row 的矩陣(未完成版)
`matrix_expansion.h`
```c=
typedef struct {
...
...
Matrix *(*create)(int rows, int cols);
} MatrixAlgo;
```
`matrix_expansion.c`
```c=
Matrix *create(int rows, int cols)
{
Matrix *m = malloc(sizeof(Matrix));
m->row = rows;
m->col = cols;
m->data = malloc(sizeof(float) * rows);
for(int i = 0; i < rows; i++)
m->data[i] = malloc(sizeof(float) * cols);
return m;
}
```
* 修改 assign 、 equal 、 mul
* `matrix_expansion.c` ==assign==
```c=
static void assign(Matrix *thiz, const Matrix *that)
{
/*map the same matrix size from that to thiz*/
thiz->row = that->row;
thiz->col = that->col;
thiz->data = malloc(sizeof(float) * thiz->row);
for(int i = 0; i < thiz->row; i++)
thiz->data[i] = malloc(sizeof(float) * thiz->col);
/*map the same data from that to thiz*/
for (int i = 0; i < thiz->row; i++)
for (int j = 0; j < thiz->col; j++)
thiz->data[i][j] = that->data[i][j];
}
```
將 thiz 矩陣的 data 使用 malloc 配置跟 that 一樣的 row 跟 col 大小，有了一樣的空間之後再賦與相同的值
* `matrix_expansion.c ==equal==
```c=
static bool equal(const Matrix *l, const Matrix *r)
{
/*if nxm matrix and axb matrix ,n!=a or m!=b you can say they
are not equal*/
if((l->row!=r->row)||(l->col!=r->col))
return false;
for (int i = 0; i < l->row; i++)
for (int j = 0; j < l->col; j++)
if (l->data[i][j] + epsilon < r->data[i][j] || r->data[i][j] + epsilon < l->data[i][j])
return false;
return true;
}
```
由於不再是只傳入 4x4 的矩陣，所以要先確認兩者是否有相同的行列數，才能開始比較兩者的值是否相同，行列數不相同就不用再比了，應為他們已經注定不是相同的陣列了。
* `matrix_expansion.c` ==mul==
```c=
bool mul(Matrix *dst, const Matrix *l, const Matrix *r)
{
/*A(nxm) matrix multiple with B(ixj) matrix,m must be equal
to i ,if m is not equal to i ,they can't mutiple.Otherwise,
the new matrix(nxj)*/
if(l->col != r->row)
return false;
dst->data = malloc(l->row * sizeof(float));
for(int i =0; i< l->row; i++)
dst->data[i]=malloc(r->col * sizeof(float));
for (int i = 0; i < l->row; i++)
for (int j = 0; j < r->col; j++)
for (int k = 0; k < l->col; k++)
dst->data[i][j] += l->data[i][k] *
r->data[k][j];
return true;
}
```
先講解矩陣乘法：
上面的圖表示出要如何計算 AB 的（1,2）和（3,3）元素，當 A 是個 4×2 矩陣和 B 是個 2×3 矩陣時。分別來自兩個矩陣的元素都依箭頭方向而兩兩配對，把每一對中的兩個元素相乘，再把這些乘積加總起來，最後得到的值即為箭頭相交位置的值。
* $(AB)_{1,2}=\sum_{r=1}^2{a_{1,r}\times b_{r,2}}=a_{1,1}\times b_{1,2}+a_{1,2}\times b_{2,2}$
* $(AB)_{3,3}=\sum_{r=1}^2{a_{3,r}\times b_{r,3}}=a_{3,1}\times b_{1,3}+a_{3,2}\times b_{2,3}$
如果 A 的行數 跟 B 的 列數，不相等那就無法做矩陣乘法，而如果能做矩陣乘法，則 AxB=C，C 矩陣的行列數為 A 的 列數 x B 的 行數
* 正式實作
```c=
MatrixAlgo *matrix_providers[] = {
&NaiveMatrixProvider,
};
int main()
{
MatrixAlgo *algo = matrix_providers[0];
Matrix dst, m, *n, fixed;
n=algo->create(3,4);
algo->assign(&m, n {
.data = {
{ 1, 2, 3, 4, },
{ 5, 6, 7, 4, },
{ 1, 2, 3, 4, },
},
});
}
```
執行過後，會出現一大堆==錯誤==，我才想到我沒有弄清楚 designated initializers 的技巧只能在初始化使用，如果不是初始階段，就無法使用這樣的方式給值，悲劇，只好重新修改 create 跟 assign。
* 修改 create
```c=
Matrix * create(int rows, int cols,float value[][cols])
{
Matrix *m = malloc(sizeof(Matrix));
m->row = rows;
m->col = cols;
m->data = malloc(sizeof(float) * rows);
for(int i = 0; i < rows; i++)
m->data[i] = malloc(sizeof(float) * cols);
for(int i=0; i<rows; i++)
for(int j=0; j<cols; j++)
m->data[i][j]=value[i][j];
return m;
}
```
將 create 多增加一個傳入的參數 value ，而 value 為矩陣要傳入的值，例如要
創照一個二維矩陣為 A（2x3）
$\begin{bmatrix}
A_{1,1} & A_{1,2} & A_{1,3} \\
A_{2,1} & A_{2,2} & A_{2,3}\end{bmatrix}=\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6\end{bmatrix}$
我們可以使用 designated initializers 的方式來建立一個二維矩陣，並將矩陣值傳給要建立的 matrix
* 實作碼
```c=
#include "..."
MatrixAlgo *matrix_providers[] = {
&NaiveMatrixProvider,
};
int main()
{
MatrixAlgo *algo = matrix_providers[0];
float value[2][3] = {
{ 1, 2, 3},
{ 4, 5, 6},
};
Matrix *A;
A=algo->create(2,3,value);
}
```
## 將 matrix 改成本身就有應對實作的函式
## 參考資料
* [你所不知道的C語言：技巧篇](https://hackmd.io/s/HyIdoLnjl#)
* [矩陣乘法](https://zh.wikipedia.org/wiki/%E7%9F%A9%E9%99%A3%E4%B9%98%E6%B3%95)
Sign in with Wallet
Connect another wallet