0
3
0
1. 云栖社区>
2. 博客>
3. 正文

## 程序设计中的计算复用(Computational Reuse)

nothingfinal 2018-03-10 19:36:00 浏览580

# 从斐波那契数列说起

 `public` `static` `ulong` `Fib(``ulong` `n)` `{` `    ``return` `(n == 1 || n == 2) ? 1 : Fib(n - 1) + Fib(n - 2);` `}`

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 `public` `static` `ulong` `Fib(``ulong` `n)` `{` `    ``if` `(n == 1 || n == 2)` `    ``{` `        ``return` `1;` `    ``}` `    ``ulong` `m1 = 1, m2 = 1;` `    ``for` `(``ulong` `i = 3; i <= n; i++)` `    ``{` `        ``m2 = m1 + m2;` `        ``m1 = m2 - m1;` `    ``}`   `    ``return` `m2;` `}`

# 矩阵乘法与Strassen算法

$A=\begin{pmatrix} a & b\\ c & d \end{pmatrix}, B=\begin{pmatrix} e & f\\ g & h \end{pmatrix}, AB=\begin{pmatrix} r & s\\ t & u \end{pmatrix}$

$r=ae+bg,s=af+bh,t=ce+dg,u=cf+dh$

$P_i=A_iB_i=(\alpha_{i1}a+\alpha_{i2}b+\alpha_{i3}c+\alpha_{i4}d)(\beta_{i1}e+\beta_{i2}f+\beta_{i3}g+\beta_{i4}h)$

$\\ P_1=A_1B_1=a(f-h)=af-ah\\ P_2=A_2B_2=(a+b)h=ah+bh\\ P_3=A_3B_3=(c+d)e=ce+de\\ P_4=A_4B_4=d(g-e)=dg-de\\ P_5=A_5B_5=(a+d)(e+h)=ae+ah+de+dh\\ P_6=A_6B_6=(b-d)(g+h)=bg+bh-dg-dh\\ P_7=A_7B_7=(a-c)(e+g)=ae+af-ce-cf$

$\\ s=P_1+P_2\\ t=P_3+P_4\\ r=P_4+P_5-P_2+P_6\\ u=P_1+P_5-P_3-P_7$

# 计算复用对软件开发的启示

 1 2 3 4 5 `foreach``(``\$items` `as` `\$k` `=> ``\$v``){` `    ``//...` `    ``\$money` `= ``\$v``->money + getTax();` `    ``//...` `}`

 1 2 3 4 5 6 `\$tax` `= getTax();` `foreach``(``\$items` `as` `\$k` `=> ``\$v``){` `    ``//...` `    ``\$money` `= ``\$v``->money + ``\$tax``;` `    ``//...` `}`

 1 `echo` `count``(``\$arr``);`

nothingfinal
+ 关注