Of course this also works with bases other than two for your underlying number system. Or with mixed approaches.
In general, there's no known algorithm for finding x^n with the fewest numbers of multiplications in time polynomial in O(log n), i.e. the size of the representation of n.
(I can't remember whether the problem was (co-)NP complete, or even how to construct the certificate to proof that the problem is in NP or perhaps co-NP. Though I'd bet on it being in NP.)
And then you can also think about balancing the number of multiplications and the number of intermediate results you have to store.
Is this what you meant: Addition Chain Exponentiation; in general, performs better than binary exponentiation, but it could be very hard to find an addition chain for a given exponent: :-)
