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 Citationer (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.

Originalsprog	Engelsk
Titel	Reversible Computetion : 10th International Conference, RC 2018 Leicester, UK, September 12–14, 2018 Proceedings
Redaktører	Jarkko Kari, Irek Ulidowski
Forlag	Springer
Publikationsdato	22 aug. 2018
Sider	253-268
ISBN (Trykt)	978-3-319-99497-0
ISBN (Elektronisk)	978-3-319-99498-7
DOI	https://doi.org/10.1007/978-3-319-99498-7_18
Status	Udgivet - 22 aug. 2018
Begivenhed	10th International Conference on Reversible Computation, RC 2018 - Leicester, Storbritannien Varighed: 12 sep. 2018 → 14 sep. 2018

Konference

Konference	10th International Conference on Reversible Computation, RC 2018
Land/Område	Storbritannien
By	Leicester
Periode	12/09/2018 → 14/09/2018

Navn	Lecture Notes in Computer Science
Vol/bind	11106
ISSN	0302-9743

Adgang til dokumentet

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

Citationsformater

Garbage-Free Reversible Multiplication and Division. / Mogensen, Torben Ægidius.
Reversible Computetion: 10th International Conference, RC 2018 Leicester, UK, September 12–14, 2018 Proceedings. red. / Jarkko Kari; Irek Ulidowski. Springer, 2018. s. 253-268 (Lecture Notes in Computer Science, Bind 11106).

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

Mogensen, TÆ 2018, Garbage-Free Reversible Multiplication and Division. i J Kari & I Ulidowski (red), Reversible Computetion: 10th International Conference, RC 2018 Leicester, UK, September 12–14, 2018 Proceedings. Springer, Lecture Notes in Computer Science, bind 11106, s. 253-268, 10th International Conference on Reversible Computation, RC 2018, Leicester, Storbritannien, 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater