Search algorithms for the multiple constant multiplications problem: Exact and approximate

摘要: This article addresses the multiplication of one data sample with multiple constants using addition/subtraction and shift operations, i.e., constant multiplications (MCM) operation. In last two decades, many efficient algorithms have been proposed to implement MCM operation fewest number addition subtraction operations. However, due NP-hardness problem, almost all existing heuristics. The main contribution this is proposal an exact depth-first search algorithm that, lower upper bound values space for problem instance, finds minimum solution consuming less computational resources than previously breadth-first algorithm. We start by describing that can be applied on real mid-size instances. also present our recently approximate solutions close able compute better bounds problem. experimental results clearly indicate efficiently large size hard instances cannot handle heuristics only find suboptimal solutions.