Fast exponentiation using the truncation operation (Q2366170)

A tight bound of \(\Theta(\sqrt k)\) time required to compute \(2^{2^ k}\) is proved for the inputs: integer \(k\) and arbitrary integer greater than \(2^{2^ k}\), the operations \(+,-,*,/,\lfloor\cdot\rfloor,\leq\) and constants \(\{0,1\}\). It is applied to the algorithms: (1) for computing \(\lfloor\log\log a\rfloor\) for all \(n\)-bit integers \(a\), in \(O(\sqrt{\log n})\) time and (2) for deciding whether an integer \(a\) in some range \([2^{2^ k},2^{2^ k+1}]\) is a perfect square in \(O(\sqrt{\log\log a})\) time.