Re: [lmi] Optimized integral power

[Greg Chicares]

On 2016-12-23 01:44, Vadim Zeitlin wrote:
> 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.

Thanks. I was sure I was missing something obvious, but that mistake
was too obvious to find easily.

> 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...

I found this reference before that one:
  http://stepanovpapers.com/PAM.pdf
In 6.5 he explains why 15 is indeed the minimal case and refers us to
TAOCP vol. 2, 4.6.3 . I believe I read that section a quarter century
ago, but forgot about it.