TY - GEN
T1 - Strength of the reversible, garbage-free 2 k ±1 multiplier
AU - Rotenberg, Eva
AU - Cranch, James
AU - Thomsen, Michael K.
AU - Axelsen, Holger Bock
PY - 2013
Y1 - 2013
N2 - Recently, a reversible garbage-free 2 k ±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. In this paper, we show that there exist infinitely many constants we cannot multiply by using cascades of 2 k ±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 2 k ±1-multipliers, and for generating the minimal cascade of 2 k ±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.
AB - Recently, a reversible garbage-free 2 k ±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. In this paper, we show that there exist infinitely many constants we cannot multiply by using cascades of 2 k ±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 2 k ±1-multipliers, and for generating the minimal cascade of 2 k ±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.
KW - constant multiplication
KW - Mersenne numbers
KW - Number theory
KW - reversible circuit design
UR - http://www.scopus.com/inward/record.url?scp=84880704415&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-38986-3-5
DO - 10.1007/978-3-642-38986-3-5
M3 - Article in proceedings
AN - SCOPUS:84880704415
SN - 9783642389856
VL - 7948 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 46
EP - 57
BT - Reversible Computation - 5th International Conference, RC 2013, Proceedings
T2 - 5th International Conference on Reversible Computation, RC 2013
Y2 - 4 July 2013 through 5 July 2013
ER -