|Re: [eigen] How to raise double to array powers in Eigen|
[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]
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_exponentiationIf 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 ;)
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-eigenI need to raise a double value to an array of integer powers, in c++ thiswould look something likeCould 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 ----------------------------------------------
|Mail converted by MHonArc 2.6.19+||http://listengine.tuxfamily.org/|