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 -