快速演算法 | 快速乘法演算法
算法優化,最主要的目的是用來減少運算時間,像是加法、乘法的數目,以及所花的運算週期。此外還能降低硬體實現所花費的成本,像是減少緩衝器的數量、重複利用相同的硬體架構。一般來說,快速演算法的設計可以透過將運算展開,並進行歸納、分析,利用運算次數更少的乘法、除法(如乘以二、除以二等左移、右移)來完成運算,達到降低運算時間的目的。而在設計的過程中,因為乘法的運算時間會遠大於加法,因此通常會以使用多少個乘法來衡量整體的運算時間。此外,因為是從硬體的角度來看,所以對於乘上2±k{displaystyle2{pmk}}、0,都可...
算法優化,最主要的目的是用來減少運算時間,像是加法、乘法的數目,以及所花的運算週期。此外還能降低硬體實現所花費的成本,像是減少緩衝器的數量、重複利用相同的硬體架構。
一般來說,快速演算法的設計可以透過將運算展開,並進行歸納、分析,利用運算次數更少的乘法、除法(如乘以二、除以二等左移、右移)來完成運算,達到降低運算時間的目的。
而在設計的過程中,因為乘法的運算時間會遠大於加法,因此通常會以使用多少個乘法來衡量整體的運算時間。此外,因為是從硬體的角度來看,所以對於乘上2±k{displaystyle 2{pm k}}、0,都可以視為不需要任何的運算時間(trivial multiplications),因為對於乘上2k{displaystyle 2{k}},或者除上2k{displaystyle 2{k}},分別只要進行左移k{displaystyle k}位元或右移k{displaystyle k}位元的運算即可達成。
簡單矩陣有關的算法優化設計[編輯][1]以下舉幾個例子,用以說明如何優化算法,使得矩陣演算能夠最優化。 1.y[1]=ax[1]+2ax[2]=[a2a][x[1]x[2]]=a(x[1]+2x[2]){displaystyle y[1]=ax[1]+2ax[2]={egin{bmatrix}a&2aend{bmatrix}}{egin{bmatrix}x[1]\x[2]end{bmatrix}}=a(x[1]+2x[2])}
從上面這個式子來看,在左邊的部分需要用到兩個乘法、一個加法,然而經過一些化簡、合併,在右邊的地方就只需要一個乘法(乘2不需要運算時間)、一個加法。
2.[y(1)y(2)]=[aaaa][x(1)x(2)]{displaystyle {egin{bmatrix}y(1)\y(2)end{bmatrix}}={egin{bmatrix}a&a\a&aend{bmatrix}}{egin{bmatrix}x(1)\x(2)end{bmatrix}}}
y(2)=y(1)=a(x(1)+x(2)){displaystyle y(2)=y(1)=a(x(1)...