Re: [eigen] How to raise double to array powers in Eigen

[Christoph Hertzberg <chtz@xxxxxxxxxxxxxxxxxxxxxxxx>]

On 18.08.2014 14:30, Chen-Pang He wrote:
> If you need no optimization and want functional programming,
> ArrayBase::unaryExpr with a homemade functor is enough.
>
> If you need optimization, because all exponents are integers,
> binary powering (aka exponentiation by squaring) is *the*
> algorithm.   We can reuse `pow(delta, (1 << k))`.

I doubt that this is (always) the most efficient way to raise a common 
base to (by?) different integer exponents. It is certainly the most 
practicable solution to compute one power, assuming multiplication is 
not too expensive and the exponent is not to big.
If multiplications are expensive (e.g. high-precision floats or whole 
matrices), then one should consider:
https://en.wikipedia.org/wiki/Addition-chain_exponentiation
If the exponent is very large, the cost of log and exp eventually is 
cheaper than EBS and ACE.

If you raise a single base to different exponents you should somehow 
exploit that many multiplications can be shared -- the best technique 
again depends on how big (and how different) the exponents are, how 
costly multiplications and branches are, etc.
E.g., if you know your exponents are in range [0 15] and each exponent 
occurs multiple times, it might be the easiest way to compute all powers 
sequentially into a look-up-table and then copy them to the result vector.

I assume, overall this is over-engineering the original problem, i.e., 
most important here is not to start premature optimization ;)

Christoph


> Cheers,
> Chen-Pang
>
> 在 2014 八月 18 週一 13:42:46，Ian Bell 寫道:
> > On Mon, Aug 18, 2014 at 1:28 PM, Christoph Hertzberg <
> > chtz@xxxxxxxxxxxxxxxxxxxxxxxx> wrote:
> >
> > > On 18.08.2014 00:23, Ian Bell wrote:
> > >
> > > > cross-posted to stack overflow...
> > >
> > > If you cross-post, could you post a link as well?
> >
> > Here's the link:
> > http://stackoverflow.com/questions/25354205/how-to-raise-double-to-array-powers-in-eigen
> >
> > >   I need to raise a double value to an array of integer powers, in c++ this
> > > > would look something like
> > >
> > > Could you be a bit more specific about the "array of integer powers" (I
> > > guess 'exponents')?
> > > If they are a sequence 0,1,2,3,... your proposed solution is definitely
> > > very inefficient. If they are of great range, with no apparent pattern, I
> > > would say the exp(log(delta)*exponent) approach is basically the most
> > > efficient solution (maybe using log2 and exp2 would be more efficient, if
> > > they were available).
> >
> > The exponents are typically in the range [0, 10), and can be sorted if that
> > is of use.  They are not necessarily linearly increasing, we might have
> > exponents 0,0,0,1,1,1,1,2,2 for instance.  Obviously it would be better to
> > short-circuit the 0 powers as well since they yield 1 again (x^0=1).  This
> > method with the exp(log(delta)*exponent) also doesn't allow you to skip
> > those powers.  I think that the >0 comparison should be cheaper than doing
> > pow(x, 0) when 0 is integer.  Especially this will be true when using exp().


--
----------------------------------------------
Dipl.-Inf., Dipl.-Math. Christoph Hertzberg
Cartesium 0.049
Universität Bremen
Enrique-Schmidt-Straße 5
28359 Bremen

Tel: +49 (421) 218-64252
----------------------------------------------