Re: [lmi] Optimized integral power

[Vadim Zeitlin]

On Thu, 22 Dec 2016 23:17:41 +0000 Greg Chicares <address@hidden> wrote:

GC> On 2016-12-22 14:45, Vadim Zeitlin wrote:
GC> > On Thu, 22 Dec 2016 02:36:49 +0000 Greg Chicares <address@hidden> wrote:
GC> > 
GC> > GC> Please take a look at commit 569b775d3ffc4afc526a83cb1a769f6d604101a8
GC> > GC> and let me know if you see any reason to keep the std::pow() 
alternative,
GC> > GC> now in a #if 0 ... #endif block. I'm inclined to remove it soon.
GC> > 
GC> >  I agree, I don't see how std::pow() could do better than what the new 
code
GC> 
GC> https://www.sgi.com/tech/stl/power.html#3
GC> | This is in fact not the minimum possible number of multiplications:
GC> | it is possible to compute the fifteenth power of x using only five
GC> | multiplications, but power(x, 15) uses six.
GC> 
GC> But we needn't worry about that. As an amusing digression, though...
GC> 
GC> Instead of looking up that example, I was going to say X^9:
GC>   X3 = X*X*X  2 total multiplications
GC>   X9 = X3*X3  3   "         "

 Sorry, X9 = X3*X3*X3, so there is one multiplication missing here.

GC> whereas with binary powers:
GC>   X2 = X*X    1 total multiplications
GC>   X4 = X2*X2  2 total multiplications
GC>   X8 = X4*X4  3 total multiplications
GC>   X9 = X*X8   4 total multiplications
GC> Am I missing something, or is Matt Austern's example not minimal
GC> as I would have expected it to be, just because that's the way I
GC> thought his mind might work?

 I didn't bother verifying this myself, but Wikipedia gives 15 as the first
power for which binary exponentiation is not optimal too, so I think it's
right:

   https://en.wikipedia.org/wiki/Addition-chain_exponentiation

 And as this page mentions, in general finding the shortest chain is
NP-hard...

 Happy birthday to Ugolyok!
VZ