Recently, a reversible garbage-free 2k ±1 constant-multiplier circuit was presented by Axelsen and Thomsen. This was the first construction of a garbage-free, reversible circuit for multiplication with non-trivial constants. At the time, the strength, that is, the range of constants obtainable by cascading these circuits, was unknown.#R##N##R##N#In this paper, we show that there exist infinitely many constants we cannot multiply by using cascades of 2k±1-multipliers; in fact, there exist infinitely many primes we cannot multiply by. Using these results, we further provide an algorithm for determining whether one can multiply by a given constant using a cascade of 2k ±1-multipliers, and for generating the minimal cascade of 2k ±1-multipliers for an obtainable constant, giving a complete characterization of the problem. A table of minimal cascades for multiplying by small constants is provided for convenience.
['Eva Rotenberg', 'James Cranch', 'Michael Kirkedal Thomsen', 'Holger Bock Axelsen']
Strength of the reversible, garbage-free 2 k ± 1 multiplier