Abstract
Here we consider a case study in reversible computing, namely, how to reversibly compute the integer square root $\left\lfloor\sqrt{x}\right\rfloor$ of an integer $x$. Starting with a simple linear time algorithm, we show how a simple reversal technique can be used to avoid saving the original number $x$ in order to recover it. This reversal technique is shown to require half the memory that would otherwise be needed to save $x$. The linear time algorithm is then refined to improve the computation time to be only logarithmically dependent on the input size, giving a $O(\log x)$ run time using $\frac{1}{2}(1+\left\lfloor\log_2{x}\right\rfloor)$ bits of memory.
Kalyan Perumalla
R&D Manager
Kalyan Perumalla is an R&D Manager with 25 years of experience. As a Federal Program Manager in Advanced Scientific Computing Research at the U.S. Dept. of Energy, Office of Science, Kalyan Perumalla manages a $100-million R&D portfolio covering AI, HPC, Quantum, SciDAC, and Basic Computer Science. He previously led advanced R&D as Distinguished Research Staff Member at the Oak Ridge National Laboratory (ORNL) developing scalable software and applications on the world’s largest supercomputers for 17 years, including as a line manager and a founding group leader. He has held senior faculty and adjunct appointments at UTK, GT, and UNL, and was an IAS Fellow at Durham University.