Strength of the reversible, garbage-free 2 k ±1 multiplier

Eva Rotenberg, James Cranch, Michael K. Thomsen, Holger Bock Axelsen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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.

Original languageEnglish
Title of host publicationReversible Computation - 5th International Conference, RC 2013, Proceedings
Volume7948 LNCS
Publication date2013
ISBN (Print)9783642389856
Publication statusPublished - 2013
Event5th International Conference on Reversible Computation, RC 2013 - Victoria, BC, Canada
Duration: 4 Jul 20135 Jul 2013


Conference5th International Conference on Reversible Computation, RC 2013
CityVictoria, BC
SponsorPacific Institute for the Mathematical Sciences, University of Victoria BC
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7948 LNCS


  • constant multiplication
  • Mersenne numbers
  • Number theory
  • reversible circuit design


Dive into the research topics of 'Strength of the reversible, garbage-free 2 k ±1 multiplier'. Together they form a unique fingerprint.

Cite this