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

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.