= Binary powering multiplication count
{title2=$C(n)=\ell+\operatorname{wt}(n)-2$}
For the optimized left-to-right <exponentiation by squaring> <algorithm>, let $\ell=\lfloor\log_2 n\rfloor+1$ be the length of the <binary expansion> of a positive <integer> $n$, and let $w=\operatorname{wt}(n)$ be its <Hamming weight>, the number of digits equal to one. There are exactly $\ell-1$ digits after the leading one, and exactly $w-1$ remaining ones. Therefore the count is
$$
S(n)=\ell-1,\qquad T(n)=w-1,\qquad C(n)=S(n)+T(n)=\ell+w-2.
$$
Here $S$ counts squarings and $T$ counts further <multiplications> by the base; \b[every squaring counts as one <multiplication> in $C$]. Assignment, digit reading, and any inversion are outside this count. The formula includes $n=1$, which requires zero <multiplications>; define $C(0)=0$ separately.
For a fixed length $\ell$, the bounds are $\ell-1\leq C(n)\leq2\ell-2$. A <power of two> reaches the lower bound because its <Hamming weight> is one; $n=2^\ell-1$ reaches the upper bound because all digits are one. For $n=13$, $\ell=4$ and $w=3$, giving $C(13)=5$. Thus the <arithmetic operation> count is $O(\log(n+1))$ in <Big O notation>, but inputs of similar magnitude can have different counts.
\Image[/binary-powering-multiplication-count.png]
{title=Exact <multiplication> counts for optimized <exponentiation by squaring> depend on binary length and <Hamming weight>}
{description=For positive exponents through $63$, dots show $C(n)=\ell+\operatorname{wt}(n)-2$, including each squaring. The dashed curves bound all counts at each binary length. Successive multiplication needs $n-1$ operations. The second panel compares squarings and further <multiplications> for exponents $8,13,15,16,31$. These are exact counts, not timing measurements.}
This is a count for the specified <algorithm>, not a claim that it always minimizes <multiplications> among all methods. For instance, at $n=15$ the count is six, but the powers with exponents $1,2,3,6,12,15$ can be built in five <multiplications>: square, multiply by $a$, square, square, then multiply by the already stored $a^3$. Saving operations this way uses a different schedule and stored intermediate powers.
Back to article page
