用於"多常數乘法問題"之有效演算法

Abstract

本論文中, 我們提出了一個對於'多常數乘法問題'而言效率頗高的演 算法. 此演算法為了節省更多的加法器(或減法器). 不僅在矩陣的各行間 搜尋'同質性子序列', 同時也在各列間搜尋. 換句話說, 此演算法適當定 義了在決定運算優先權時每個子序列的'比重', 並在每一步驟都選擇花費 最少的子序列, 矩陣會先經過前置處理以便增強稍後正式執行的演算法的 效能. 若將矩陣視為彈簧, 則此前置處裡動作會非常類似將原先作用在彈 簧上的拉力除去, 使彈簧處於最鬆弛狀態之舉動. 此外, 我們還提出了一 個'伸縮性'演算法, 它利用了'取負值'與'等比脹縮'兩項技巧以使'彈簧 法'得到更進一步的改善. In this thesis, we propose an efficient solution for the multiple constant multiplication (MCM) problem. Regarding the matrix as a spring , the algorithm aims at adjusting the spring into its most relaxing situation. The algoritm can thus search the common-subexpressions not only across the columns of the digit matrix but also across the rows to reduce the number of additions and subtrac-tions. Besides, an elasticizing algorithm which exploits the negation and scal-ing techniques is proposed to improve the impact of the spring algorithm fur-ther. In other words, the structure of the matrix is pre-manipulated so as to enhance the efficiency of the optimization algorithm being exeecuted later. Theexperimental results are very promising.