Multi-Exponentiation Implementation

Is anyone aware of an implemented multi-exponentiation alg开发者_如何学Corithm? I'm looking for something that given vectors A, B would compute the product of A[i]^B[i] using some of the fast algorithms out there.

Thanks!

The following assumes that your data is floating point. If you have instead multi-precision integers, please specify your requirements.

The clean numerical way is of course to take the log first. Indeed, partial products can easily under/overflow even if the result is finite.

The idiomatic corresponding C++ program is:

#include <cmath>
#include <functional>
#include <numeric>

double f(double x, double y)
{
    return y * std::log(x);
}

template <typename I, typename J>
double multi_exponentiation(I a0, I an, J b0)
{
    return std::exp(std::inner_product(a0, an, b0, 0., std::plus<double>(), f));
}

// Example program
int main()
{
    std::vector<double> a, b;
    ...
    double e = multi_exponentiation(a.begin(), a.end(), b.begin());
}

Using inner_product instead of writing the loop yourself has the advantage that once you know that performance is a problem, you can replace the inner_product algorithm with a parallel_inner_product algorithm provided by a third-party library (or write one yourself).

How fast does this have to be? Depending on the size of your algorithm, the power function shouldn't be too much of a bottleneck.

You would write a simple function such as the following:

Vector VectorPower( Vector vec1, Vector vec2 )
{
      assert(vec1.length() == vec2.length());

      Vector vecAns( vec1.length() );

      for( unsigned int i = 0; i < vec1.length(); i++ )
      {
           vecAns[i] = pow( vec1[i], vec2[i] );
      }

      return vecAns;

}

Most of the time this will be efficient enough for your application. If you were implementing a square root or some other transcendental function, then you would have too look at optimization.

Also, some processors are optimized for arbitrary integral powers, and GPUs certainly are (although that's not much help unless this is a Graphics related post, and isn't tagged as such).

Hope this answers your question :)

Have you tried tommath (not sure it meets your performance requirement)? Its multi-precision integer arith library!