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

Eva Rotenberg; James Cranch; Michael Kirkedal Thomsen; Holger Bock Axelsen

doi:10.1007/978-3-642-38986-3_5

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

Eva Rotenberg, James Cranch, Michael Kirkedal Thomsen, Holger Bock Axelsen

Datalogisk Institut

Abstract

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.

Originalsprog	Engelsk
Titel	Reversible Computation : 5th International Conference, RC 2013, Victoria, BC, Canada, July 4-5, 2013. Proceedings
Redaktører	Gerhard W. Dueck, D. Michael Miller
Antal sider	12
Forlag	Springer
Publikationsdato	2013
Sider	46-57
ISBN (Trykt)	978-3-642-38985-6
ISBN (Elektronisk)	978-3-642-38986-3
DOI	https://doi.org/10.1007/978-3-642-38986-3_5
Status	Udgivet - 2013
Begivenhed	5th International Conference on Reversible Computation - Victoria, Canada Varighed: 4 jul. 2013 → 5 jul. 2013 Konferencens nummer: 5

Konference

Konference	5th International Conference on Reversible Computation
Nummer	5
Land/Område	Canada
By	Victoria
Periode	04/07/2013 → 05/07/2013

Navn	Lecture notes in computer science
Vol/bind	7948
ISSN	0302-9743

Adgang til dokumentet

10.1007/978-3-642-38986-3_5

Citationsformater

Strength of the reversible, garbage-free 2^k ± 1 multiplier. / Rotenberg, Eva; Cranch, James; Thomsen, Michael Kirkedal et al.
Reversible Computation: 5th International Conference, RC 2013, Victoria, BC, Canada, July 4-5, 2013. Proceedings. red. / Gerhard W. Dueck; D. Michael Miller. Springer, 2013. s. 46-57 (Lecture notes in computer science, Bind 7948).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Rotenberg, E, Cranch, J, Thomsen, MK & Axelsen, HB 2013, Strength of the reversible, garbage-free 2^k ± 1 multiplier. i GW Dueck & DM Miller (red), Reversible Computation: 5th International Conference, RC 2013, Victoria, BC, Canada, July 4-5, 2013. Proceedings. Springer, Lecture notes in computer science, bind 7948, s. 46-57, 5th International Conference on Reversible Computation, Victoria, Canada, 04/07/2013. https://doi.org/10.1007/978-3-642-38986-3_5

@inproceedings{2408da8ff94848b4a67fc7c6bb3e4b12,

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

abstract = "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.",

author = "Eva Rotenberg and James Cranch and Thomsen, {Michael Kirkedal} and Axelsen, {Holger Bock}",

year = "2013",

doi = "10.1007/978-3-642-38986-3_5",

language = "English",

isbn = "978-3-642-38985-6",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "46--57",

editor = "Dueck, {Gerhard W.} and Miller, {D. Michael}",

booktitle = "Reversible Computation",

note = "5th International Conference on Reversible Computation ; Conference date: 04-07-2013 Through 05-07-2013",

}

TY - GEN

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

AU - Rotenberg, Eva

AU - Cranch, James

AU - Thomsen, Michael Kirkedal

AU - Axelsen, Holger Bock

N1 - Conference code: 5

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.

U2 - 10.1007/978-3-642-38986-3_5

DO - 10.1007/978-3-642-38986-3_5

M3 - Article in proceedings

SN - 978-3-642-38985-6

T3 - Lecture notes in computer science

SP - 46

EP - 57

BT - Reversible Computation

A2 - Dueck, Gerhard W.

A2 - Miller, D. Michael

PB - Springer

T2 - 5th International Conference on Reversible Computation

Y2 - 4 July 2013 through 5 July 2013

ER -

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

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater

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