Multiplierless multiple constant multiplication

TLDR

Multiplier blocks for fixed‑point constants use only additions, subtractions, and shifts; generating such blocks is the multiple constant multiplication (MCM) problem, which is NP‑complete to optimize for minimal operations. We propose a new algorithm for the MCM problem that reduces the number of additions and subtractions by up to 20% compared to the best known algorithm. We present our algorithm using a unifying formal framework for the best, graph‑based MCM algorithms and provide a detailed runtime analysis and experimental evaluation. The algorithm achieves up to 20% fewer operations, is not limited by constant bitwidths, handles up to 100 32‑bit constants within acceptable time, and its implementation is available online.

Abstract

A variable can be multiplied by a given set of fixed-point constants using a multiplier block that consists exclusively of additions, subtractions, and shifts. The generation of a multiplier block from the set of constants is known as the multiple constant multiplication (MCM) problem. Finding the optimal solution, namely, the one with the fewest number of additions and subtractions, is known to be NP-complete. We propose a new algorithm for the MCM problem, which produces solutions that require up to 20% less additions and subtractions than the best previously known algorithm. At the same time our algorithm, in contrast to the closest competing algorithm, is not limited by the constant bitwidths. We present our algorithm using a unifying formal framework for the best, graph-based MCM algorithms and provide a detailed runtime analysis and experimental evaluation. We show that our algorithm can handle problem sizes as large as 100 32-bit constants in a time acceptable for most applications. The implementation of the new algorithm is available at www.spiral.net.