An approximate algorithm for the multiple constant multiplications problem

Multiple constant multiplications (MCM) problem that is to obtain the minimum number of addition/subtraction operations required to implement the constant multiplications finds itself and its variants in many applications, such as finite impulse response (FIR) filters, linear signal transforms, and computer arithmetic. There have been a number of efficient algorithms proposed for the MCM problem. However, due to the NP-hardness of the problem, the proposed algorithms have been heuristics and cannot guarantee the minimum solution. In this paper, we introduce an approximate algorithm that can ensure the minimum solution on more instances than the previously proposed heuristics and can be extended to an exact algorithm using an exhaustive search. The approximate algorithm has been applied on a comprehensive set of instances including FIR filter and randomly generated hard instances, and compared with the previously proposed efficient heuristics. It is observed from the experimental results that the proposed approximate algorithm finds competitive and better results than the prominent heuristics.