Algorithm to compute $n^{\log k}$ in $O(\log\log k)$ I was given this exercise and I think I have to use a variation of Gauss repeated squaring, but I can not figure out how to produce $\log\log k$ in steps, like when you divide $k$ by $2$ to compute $\log k$ in steps. Any ideas?
The idea is to use repeated squaring. Compute $n,n^2,n^4,\ldots n^{\log k}$. To compute $n^{2^i}$ use the fact that $n^{2^i} = n^{2^{i-1}} n^{2^{i-1}}$. Note that the answer of $n^{2^{i-1}}$ will be known in the $i$th iteration.