2006年3月26日 星期日

Strassen's algorithm for matrix multiplication

簡單的比較 一般的矩陣運算 以及 Strassen's algorithm

{ r s } { a b } { e f }
{ t u } = { c d } * { g h }

一般的矩陣運算: Θ(n^3)
r = ae + bg
s = af + bh
t = ce + dg
u = cf + dh
總共 4 個加法運算 8 個乘法運算

Strassen's algorithm: Θ(n^lg7)
P1 = a * ( f - h )
P2 = ( a + b ) * h
=> s = P1 + P2
P3 = ( c + d ) * e
P4 = d * ( g - e )
=> t = P3 + P4
P5 = ( a + d ) * ( e + h )
P6 = ( b - d ) * ( g + h )
=> r = P5 + P4 - P2 + P6
P7 = ( a - c ) * ( e + f )
=> u = P5 + P1 - P3 - P7
總共 18 個加法運算 7 個乘法運算

在一般的 CPU 中乘法所需的運算量較大,所以才會造成 Strassen's algorithm 比較快 (應該吧?)

sha1sum on Mac OS X

最近在抓 Fedora Core 5 的 iso 檔
需要 sha1sum 的檢查
如果有系統上有裝 Fink 的話
只要再裝上 textutils 就可以了
sudo apt-get install textutils
不用再去抓什麼來路不明的軟體

2006年3月25日 星期六

你永遠不知道意外會在什麼時候發生

剛剛做了一件讓我後悔莫及的事
如果再給我一次機會我希望可以備份在光碟上面
最近幫我的 Notebook 換了一顆硬碟
原本的硬碟已經出現壞軌現象
結果在將原本的資料用 tar czf 起來後
傳到另外一台電腦上
接著想要解開裡面某部份的檔案
不小心把指令下錯了
tar czf bakup.tgz files
結果當然是原本的資料完了... Orz
現在真的是欲哭無淚啊 T.T
電視上的保險有在保電腦資料的嗎 XD