Garbage-Free Reversible Multiplication and Division

Torben Ægidius Mogensen

doi:10.1007/978-3-319-99498-7_18

Garbage-Free Reversible Multiplication and Division

1 Citation (Scopus)

Abstract

We present a circuit design for garbage-free reversible multiplier. Given inputs A, B and R, where We present a circuit design for garbage-free reversible multiplier. Given inputs A, B and R, where 0 ≤ B < 2^m and 0 ≤ R < A < 2n, the circuit outputs A and P = A· B + R. Applied in reverse, the circuit takes as input A and P, where 0 < A < 2ⁿ and 0 ≤ P < 2^mA, and outputs A, B = P/A and R = P%A. The circuit uses a total of two ancilla bits. The circuit is constructed as a sequence of m modified ripple-carry adders and comparators, both of which have O(n) gate delay, so the multiplier has O(m×n) gate delay, but this can be improved to O(m×log(n)) by using a modified carry-lookahead adder and an O(log(n)) comparator, both of which are described in the paper. The cost of reducing the gate delay to O(m×log(n)) is O(n) added ancilla bits and a larger gate count.

Original language	English
Title of host publication	Reversible Computetion : 10th International Conference, RC 2018 Leicester, UK, September 12–14, 2018 Proceedings
Editors	Jarkko Kari, Irek Ulidowski
Publisher	Springer
Publication date	22 Aug 2018
Pages	253-268
ISBN (Print)	978-3-319-99497-0
ISBN (Electronic)	978-3-319-99498-7
DOIs	https://doi.org/10.1007/978-3-319-99498-7_18
Publication status	Published - 22 Aug 2018
Event	10th International Conference on Reversible Computation, RC 2018 - Leicester, United Kingdom Duration: 12 Sept 2018 → 14 Sept 2018

Conference

Conference	10th International Conference on Reversible Computation, RC 2018
Country/Territory	United Kingdom
City	Leicester
Period	12/09/2018 → 14/09/2018

Series	Lecture Notes in Computer Science
Volume	11106
ISSN	0302-9743

Access to Document

10.1007/978-3-319-99498-7_18

Cite this

Garbage-Free Reversible Multiplication and Division. / Mogensen, Torben Ægidius.

Reversible Computetion: 10th International Conference, RC 2018 Leicester, UK, September 12–14, 2018 Proceedings. ed. / Jarkko Kari; Irek Ulidowski. Springer, 2018. p. 253-268 (Lecture Notes in Computer Science, Vol. 11106).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Mogensen, TÆ 2018, Garbage-Free Reversible Multiplication and Division. in J Kari & I Ulidowski (eds), Reversible Computetion: 10th International Conference, RC 2018 Leicester, UK, September 12–14, 2018 Proceedings. Springer, Lecture Notes in Computer Science, vol. 11106, pp. 253-268, 10th International Conference on Reversible Computation, RC 2018, Leicester, United Kingdom, 12/09/2018. https://doi.org/10.1007/978-3-319-99498-7_18

@inproceedings{d6293ef4147d4c76925c9e5475c4704c,

title = "Garbage-Free Reversible Multiplication and Division",

abstract = "We present a circuit design for garbage-free reversible multiplier. Given inputs A, B and R, where We present a circuit design for garbage-free reversible multiplier. Given inputs A, B and R, where 0 ≤ B < 2m and 0 ≤ R < A < 2n, the circuit outputs A and P = A· B + R. Applied in reverse, the circuit takes as input A and P, where 0 < A < 2n and 0 ≤ P < 2mA, and outputs A, B = P/A and R = P%A. The circuit uses a total of two ancilla bits. The circuit is constructed as a sequence of m modified ripple-carry adders and comparators, both of which have O(n) gate delay, so the multiplier has O(m×n) gate delay, but this can be improved to O(m×log(n)) by using a modified carry-lookahead adder and an O(log(n)) comparator, both of which are described in the paper. The cost of reducing the gate delay to O(m×log(n)) is O(n) added ancilla bits and a larger gate count.",

author = "Mogensen, {Torben {\AE}gidius}",

year = "2018",

month = aug,

day = "22",

doi = "10.1007/978-3-319-99498-7_18",

language = "English",

isbn = "978-3-319-99497-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "253--268",

editor = "Kari, {Jarkko } and Ulidowski, {Irek }",

booktitle = "Reversible Computetion",

note = "10th International Conference on Reversible Computation, RC 2018 ; Conference date: 12-09-2018 Through 14-09-2018",

}

TY - GEN

T1 - Garbage-Free Reversible Multiplication and Division

AU - Mogensen, Torben Ægidius

PY - 2018/8/22

Y1 - 2018/8/22

N2 - We present a circuit design for garbage-free reversible multiplier. Given inputs A, B and R, where We present a circuit design for garbage-free reversible multiplier. Given inputs A, B and R, where 0 ≤ B < 2m and 0 ≤ R < A < 2n, the circuit outputs A and P = A· B + R. Applied in reverse, the circuit takes as input A and P, where 0 < A < 2n and 0 ≤ P < 2mA, and outputs A, B = P/A and R = P%A. The circuit uses a total of two ancilla bits. The circuit is constructed as a sequence of m modified ripple-carry adders and comparators, both of which have O(n) gate delay, so the multiplier has O(m×n) gate delay, but this can be improved to O(m×log(n)) by using a modified carry-lookahead adder and an O(log(n)) comparator, both of which are described in the paper. The cost of reducing the gate delay to O(m×log(n)) is O(n) added ancilla bits and a larger gate count.

AB - We present a circuit design for garbage-free reversible multiplier. Given inputs A, B and R, where We present a circuit design for garbage-free reversible multiplier. Given inputs A, B and R, where 0 ≤ B < 2m and 0 ≤ R < A < 2n, the circuit outputs A and P = A· B + R. Applied in reverse, the circuit takes as input A and P, where 0 < A < 2n and 0 ≤ P < 2mA, and outputs A, B = P/A and R = P%A. The circuit uses a total of two ancilla bits. The circuit is constructed as a sequence of m modified ripple-carry adders and comparators, both of which have O(n) gate delay, so the multiplier has O(m×n) gate delay, but this can be improved to O(m×log(n)) by using a modified carry-lookahead adder and an O(log(n)) comparator, both of which are described in the paper. The cost of reducing the gate delay to O(m×log(n)) is O(n) added ancilla bits and a larger gate count.

U2 - 10.1007/978-3-319-99498-7_18

DO - 10.1007/978-3-319-99498-7_18

M3 - Article in proceedings

SN - 978-3-319-99497-0

T3 - Lecture Notes in Computer Science

SP - 253

EP - 268

BT - Reversible Computetion

A2 - Kari, Jarkko

A2 - Ulidowski, Irek

PB - Springer

T2 - 10th International Conference on Reversible Computation, RC 2018

Y2 - 12 September 2018 through 14 September 2018

ER -

Garbage-Free Reversible Multiplication and Division

Abstract

Conference

Access to Document

Fingerprint

Cite this