Multipliers can be relatively large pieces of hardware. We can multiply two n-bit integers with a simple long multiplication algorithm using a sequence of n n-bit additions. If we want to do the multiplication in a single cycle, we will need O(n^2) gates to do all the n-bit multiplications in one cycle. There are faster multiplications for large values of n, but for smaller values of n, such as n < 64, some version of long multiplication is typically more efficient.
A common operation in many algorithms in signal processing, cryptography, and image processing is to multiply by a known constant. Hardware that multiplies an n-bit value by an n-bit constant can often be smaller and faster then a general-purpose multiplier. Multiplication by a constant can be divided into a sequence of shifts and adds that result in simpler hardware. For example, if we have an input value x and a constant 45, we could compute 45x with the following sequence.
9x = 8(x) + x; 45x = 9x + 4(9x);
In other words we can multiply an input times the constant 45 using just two adds. We also need shift operations (that is multiplications by 2, 4, 8, 16, 32, etc.) but constant shifts can by done in hardware just by selecting bits, so the cost is close to zero. Finding the lowest cost sequence of shifts and adds that can multiply by a given constant is known as the single constant multiplier (SCM) problem. The time complexity of the SCM problem is still unknown, but there is a popular conjecture that the problem is NP hard.
Several algorithms have been proposed for SCM (for example https://doi.org/10.1145/1837274.1837424), using heuristics or exhaustive search to try to find a minimal constant multiplier. However, there is no publicly available implementation of these algorithms for those who need to find a constant multiplier for a specific problem. The goal of this project is to create a program that can generate a small or minimal constant multiplier for any 32-bit, 64-bit or 128-bit unsigned integer constant. The implementation should be in a mainstream programming language such as C, C++, Java or Python.