Reversibly Finding the Square Root of an Integer

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.