= Coupled binary exponentiation
{title2=$p x^k=A^n,\quad q y^l=B^m$}
To compute two nonnegative <integer> powers in one <while loop>, maintain a separate accumulator, current base and remaining exponent for each <exponentiation by squaring>. The paired <loop invariant> is $p x^k=A^n$ and $q y^l=B^m$. For each positive remaining exponent, transfer its odd factor to its accumulator and halve the exponent while squaring its base. A zero remaining exponent is left unchanged. The mathematical <integer> $k+l$ is a <loop variant>: at least one positive term strictly decreases in every iteration. Both powers are therefore complete when the loop stops. The iteration count is $O(\log(\max(n,m)+1))$, with <constant space> and a constant number of <multiplications> per iteration. This is an exact-arithmetic identity; <floating-point rounding> introduces a separate error in a numerical implementation.
Back to article page
