Reversible Karatsuba's Algorithm
| dc.creator | Kowada,Luis Antonio Brasil | |
| dc.creator | Portugal,Renato | |
| dc.creator | Miraglia Herrera de Figueiredo,Celina | |
| dc.date | 2006 | |
| dc.date.accessioned | 2024-02-06T12:54:23Z | |
| dc.date.available | 2024-02-06T12:54:23Z | |
| dc.description | Karatsuba discovered the first algorithm that accomplishes multiprecision integer multiplication with complexity below that of the grade-school method. This algorithm is implemented nowadays in computer algebra systems using irreversible logic. In this paper we describe reversible circuits for the Karatsuba's algorithm and analyze their computational complexity. We discuss garbage disposal methods and compare with the well known Bennett's schemes. These circuits can be used in reversible computers which have the advantage of being very efficient in terms of energy consumption. The algorithm can also be used in quantum computers and is an improvement of previous circuits for the same purpose described in the literature. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-012-05-0499 | |
| dc.identifier | https://lib.jucs.org/article/28614/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/9022 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 12(5): 499-511 | |
| dc.subject | reversible computing | |
| dc.subject | reversible circuit | |
| dc.subject | arithmetic operations | |
| dc.subject | multiplier | |
| dc.title | Reversible Karatsuba's Algorithm | |
| dc.type | Research Article |