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

[Ian Bell <ian.h.bell@xxxxxxxxx>]

Yeah actually that (pre-calculation) probably is the best/fastest solution, and is a good idea for my other code too.  The set of exponents is pretty small.

New idea:
1. Cache the set of exponents in a std::map<int, double>
2. Calculate necessary powers by pow(double, int) standard function, store in the map
3. Fill ArrayXd with the values calculated from the map.

Thanks for the ideas and the discussion!!

On Tue, Aug 19, 2014 at 3:27 PM, Christoph Hertzberg <chtz@xxxxxxxxxxxxxxxxxxxxxxxx> wrote:

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