= Simultaneous exponentiation by squaring
{title2=$p_j u_j^k=a_j^n$}
Several powers with one nonnegative exponent can share a single exponent-halving loop. For bases $a_j$, maintain accumulators $p_j$, current bases $u_j$ and a remaining exponent $k$, with <loop invariants> $p_j u_j^k=a_j^n$. For an odd $k$, multiply every accumulator by its current base; square every current base and halve $k$. The equalities are preserved in parallel, and the nonnegative <loop variant> $k$ strictly decreases. For a fixed number of bases this uses $O(\log(n+1))$ arithmetic operations and one loop, while keeping each base in the intended numeric type.
Back to article page
