Editing Exponentiation by squaring (section)

==Alternatives and generalizations==
{{main|Addition-chain exponentiation}}
Exponentiation by squaring can be viewed as a suboptimal [[addition-chain exponentiation]] algorithm: it computes the exponent by an [[addition chain]] consisting of repeated exponent doublings (squarings) and/or incrementing exponents by ''one'' (multiplying by ''x'') only. More generally, if one allows ''any'' previously computed exponents to be summed (by multiplying those powers of ''x''), one can sometimes perform the exponentiation using fewer multiplications (but typically using more memory). The smallest power where this occurs is for ''n'' = 15:

: <math>x^{15} = x \times (x \times [x \times x^2]^2)^2</math> (squaring, 6 multiplies),
: <math>x^{15} = x^3 \times ([x^3]^2)^2</math> (optimal addition chain, 5 multiplies if ''x''<sup>3</sup> is re-used).

In general, finding the ''optimal'' addition chain for a given exponent is a hard problem, for which no efficient algorithms are known, so optimal chains are typically used for small exponents only (e.g. in [[compiler]]s where the chains for small powers have been pre-tabulated). However, there are a number of [[heuristic]] algorithms that, while not being optimal, have fewer multiplications than exponentiation by squaring at the cost of additional bookkeeping work and memory usage. Regardless, the number of multiplications never grows more slowly than [[Big-O notation|&Theta;]](log ''n''), so these algorithms improve asymptotically upon exponentiation by squaring by only a constant factor at best.