Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

JUCS - Journal of Universal Computer Science

Reversible Karatsuba's Algorithm

Luis Antônio Brasil Kowada, Renato Portugal, Celina M.H. de Figueiredo

Published Jan 1, 2006• 18 citations
Publisher

Abstract

Abstract: 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.

DOI
10.3217/jucs-012-05-0499

Related papers

Optimization of multiplier in reversible logic

N. Bhuvaneswary, Adhi Lakshmi

Reversible logic is leading area in power consumption.Based on its application, its emerging trend in power consumption.In ideal situations, reversible circuit yield nil power.Different methods of multiplier optimized in this paper.Like quantum computers, multipliers required to develop computational units.In the paper, two different methods of multiplier developed with very large bit width.Based on partial products hierarchical method is developed.Another method is Karatsuba's algorithm developed based on divide and conquers method.Finally, we compare the results of both two methods.The projected reversible multipliers are enhanced in terms of quantum cost, number of constant inputs, number of garbage outputs and complexity in hardware.In nanotechnology applications this multiplier can be used to construct complex system.

3C Tecnología_Glosas de innovación aplicadas a la pyme•Nov 30, 2021•1 citation

Improved reversible and quantum circuits for Karatsuba-based integer multiplication

Alex Parent, Martin Roetteler, Michele Mosca

Integer arithmetic is the underpinning of many quantum algorithms, with applications ranging from Shor's algorithm over HHL for matrix inversion to Hamiltonian simulation algorithms. A basic objective is to keep the required resources to implement arithmetic as low as possible. This applies in particular to the number of qubits required in the implementation as for the foreseeable future this number is expected to be small. We present a reversible circuit for integer multiplication that is inspired by Karatsuba's recursive method. The main improvement over circuits that have been previously reported in the literature is an asymptotic reduction of the amount of space required from $O(n^{1.585})$ to $O(n^{1.427})$. This improvement is obtained in exchange for a small constant increase in the number of operations by a factor less than $2$ and a small asymptotic increase in depth for the parallel version. The asymptotic improvement are obtained from analyzing pebble games on complete ternary trees.

arXiv:1706.03419•Leibniz international proceedings in informatics•Jun 11, 2017•24 citations

Quantum circuits for Toom-Cook multiplication

Srijit Dutta, Debjyoti Bhattacharjee, Anupam Chattopadhyay

In this paper, we report efficient quantum circuits for integer multiplication using the Toom-Cook algorithm. By analyzing the recursive tree structure of the algorithm, we obtained a bound on the count of Toffoli gates and qubits. These bounds are further improved by employing reversible pebble games through uncomputing the intermediate results. The asymptotic bounds for different performance metrics of the proposed quantum circuit are superior to the prior implementations of multiplier circuits using schoolbook and Karatsuba algorithms.

arXiv:1805.02342•Physical Review A•Jul 12, 2018•29 citations

Two Novel Design Approaches for Optimized Reversible Multiplier Circuit

Sadia Afrin, Fahim Shihab Shan, Zarrin Tasnim Sworna

Reversible logic is one of the stepping stones in low power circuit design. Due to low power consumption and minimum bit loss features, future quantum computing devices are estimated to be reversible. Compared to addition, multiplication is a step further in the ladder of abstraction. It is the manifestation of a pattern generation system capable of representing 3-D patterns and transforming them by rotation, projection, reflection etc. The use of reversible logic in this field can reduce the wastage of energy, power and improve many factors. In this paper, an efficient multiplication algorithm has been proposed which is a modification of conventional shift-and-add multiplication method. Implementing proposed algorithm two reversible multiplier circuit has been proposed. For producing partial product, Peres gate has been used for the first design and Toffoli gate for the second design. Both of the circuits use Peres gate as Half-Adder and HNG gate as Full-Adder for addition of partial products. The first design is improved radically in terms of quantum cost, delay and the second design is notably improved in terms of transistor count and hardware complexity compared to the existing best known multipliers.

IEEE International WIE Conference on Electrical and Computer Engineering•Nov 1, 2019•3 citations

A Review on Reversible Logic Gates and their Implementation

Raghava Garipelly, P. Madhu Kiran, A. Santhosh Kumar

Abstract — Reversible logic is one of the most vital issue at present time and it has different areas for its application, those are low power CMOS, quantum computing, nanotechnology, cryptography, optical computing, DNA computing, digital signal processing (DSP), quantum dot cellular automata, communication, computer graphics. It is not possible to realize quantum computing without implementation of reversible logic. The main purposes of designing reversible logic are to decrease quantum cost, depth of the circuits and the number of garbage outputs. This paper provides the basic reversible logic gates, which in designing of more complex system having reversible circuits as a primitive component and which can execute more complicated operations using quantum computers. The reversible circuits form the basic building block of quantum computers as all quantum operations are reversible. This paper presents the data relating to the primitive reversible gates which are available in literature and helps researches in designing higher complex computing circuits using reversible gates.

•Jan 29, 2014•66 citations

Reversible implementation of novel multiply accumulate (MAC) unit

Raman M Swaraj, Kumar K Arun, Reddy K Srinivas

In almost all the Digital Signal Processing (DSP) applications, the vital operations involve multiplications and accumulations. Consequently, there is a demand for dedicated hardware in processors to enhance the speed with which these multiplications and accumulations are performed. In the present world of irreversible circuits, the Multiply Accumulate Unit multiplies the two operands, adds the product to the previously accumulated result and stores back the new result in the Accumulator all in a single clock cycle. On the other hand, implementation of digital circuits in reversible logic is gaining popularity with the arrival of quantum computing and reversible logic. In this paper, we propose a novel Reversible Multiply Accumulate (MAC) unit. We also build a Reversible Vedic MAC unit and compare various possible implementations of the reversible MAC unit in terms of Quantum Cost, number of Garbage Outputs and Depth.

International Conference on Communication, Information & Computing Technology•Oct 1, 2012•6 citations
Abstract: 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.
Reversible logic is leading area in power consumption.Based on its application, its emerging trend in power consumption.In ideal situations, reversible circuit yield nil power.Different methods of multiplier optimized in this paper.Like quantum computers, multipliers required to develop computational units.In the paper, two different methods of multiplier developed with very large bit width.Based on partial products hierarchical method is developed.Another method is Karatsuba's algorithm developed based on divide and conquers method.Finally, we compare the results of both two methods.The projected reversible multipliers are enhanced in terms of quantum cost, number of constant inputs, number of garbage outputs and complexity in hardware.In nanotechnology applications this multiplier can be used to construct complex system.
Integer arithmetic is the underpinning of many quantum algorithms, with applications ranging from Shor's algorithm over HHL for matrix inversion to Hamiltonian simulation algorithms. A basic objective is to keep the required resources to implement arithmetic as low as possible. This applies in particular to the number of qubits required in the implementation as for the foreseeable future this number is expected to be small. We present a reversible circuit for integer multiplication that is inspired by Karatsuba's recursive method. The main improvement over circuits that have been previously reported in the literature is an asymptotic reduction of the amount of space required from O(n1.585)O(n^{1.585})O(n1.585) to O(n1.427)O(n^{1.427})O(n1.427). This improvement is obtained in exchange for a small constant increase in the number of operations by a factor less than 222 and a small asymptotic increase in depth for the parallel version. The asymptotic improvement are obtained from analyzing pebble games on complete ternary trees.
In this paper, we report efficient quantum circuits for integer multiplication using the Toom-Cook algorithm. By analyzing the recursive tree structure of the algorithm, we obtained a bound on the count of Toffoli gates and qubits. These bounds are further improved by employing reversible pebble games through uncomputing the intermediate results. The asymptotic bounds for different performance metrics of the proposed quantum circuit are superior to the prior implementations of multiplier circuits using schoolbook and Karatsuba algorithms.
Reversible logic is one of the stepping stones in low power circuit design. Due to low power consumption and minimum bit loss features, future quantum computing devices are estimated to be reversible. Compared to addition, multiplication is a step further in the ladder of abstraction. It is the manifestation of a pattern generation system capable of representing 3-D patterns and transforming them by rotation, projection, reflection etc. The use of reversible logic in this field can reduce the wastage of energy, power and improve many factors. In this paper, an efficient multiplication algorithm has been proposed which is a modification of conventional shift-and-add multiplication method. Implementing proposed algorithm two reversible multiplier circuit has been proposed. For producing partial product, Peres gate has been used for the first design and Toffoli gate for the second design. Both of the circuits use Peres gate as Half-Adder and HNG gate as Full-Adder for addition of partial products. The first design is improved radically in terms of quantum cost, delay and the second design is notably improved in terms of transistor count and hardware complexity compared to the existing best known multipliers.
Abstract — Reversible logic is one of the most vital issue at present time and it has different areas for its application, those are low power CMOS, quantum computing, nanotechnology, cryptography, optical computing, DNA computing, digital signal processing (DSP), quantum dot cellular automata, communication, computer graphics. It is not possible to realize quantum computing without implementation of reversible logic. The main purposes of designing reversible logic are to decrease quantum cost, depth of the circuits and the number of garbage outputs. This paper provides the basic reversible logic gates, which in designing of more complex system having reversible circuits as a primitive component and which can execute more complicated operations using quantum computers. The reversible circuits form the basic building block of quantum computers as all quantum operations are reversible. This paper presents the data relating to the primitive reversible gates which are available in literature and helps researches in designing higher complex computing circuits using reversible gates.
In almost all the Digital Signal Processing (DSP) applications, the vital operations involve multiplications and accumulations. Consequently, there is a demand for dedicated hardware in processors to enhance the speed with which these multiplications and accumulations are performed. In the present world of irreversible circuits, the Multiply Accumulate Unit multiplies the two operands, adds the product to the previously accumulated result and stores back the new result in the Accumulator all in a single clock cycle. On the other hand, implementation of digital circuits in reversible logic is gaining popularity with the arrival of quantum computing and reversible logic. In this paper, we propose a novel Reversible Multiply Accumulate (MAC) unit. We also build a Reversible Vedic MAC unit and compare various possible implementations of the reversible MAC unit in terms of Quantum Cost, number of Garbage Outputs and Depth.