Almost all modern processors provide special-purpose instructions for integer multiplication. However, some applications require integer values that are larger than fit in a single machine word, such as 256 bit integers. We can multiply these big integer values using a sequence of smaller multiplies. For example, multiplying two 256-bit integer values might be completed with a sequence of sixteen 64-bit multiplies and additions. However, if one of the two 256-bit integers is a constant value, it may be possible to complete the computation using fewer 64-bit multiplication operations.
There is a large existing literature on finding miminum sequences of shifts and adds to implement constant multiplication in hardware. These approaches compute intermediate products along the way, and find a reduced-cost sequence of shifts and adds by combining these intermediate products. A similar approach should be possible for multiplication by big multi-word integers. The goal of the project is to adapt one or more existing approaches of minimum constant multiplication to the case where we have multiplication operators, but smaller than the word-size of the integers to be multiplied.