多重求幂实现

Question

有没有人知道一种已实现的多重求幂算法？我正在寻找一些东西，给定向量A，B，可以使用一些快速算法来计算Ai^Bi的乘积。

谢谢!

Answer 1

下面假设你的数据是浮点型的。如果您使用的是多精度整数，请指定您的要求。

当然，干净的数值方法是首先获取日志。事实上，即使结果是有限的，部分乘积也可以很容易地欠/溢出。

惯用的对应C++程序是：

#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());
}

使用inner_product而不是自己编写循环的好处是，一旦您知道性能有问题，就可以用第三方库提供的parallel_inner_product算法替换inner_product算法(或者自己编写)。

Answer 2

这需要多快？根据算法的大小，幂函数不应该成为太多的瓶颈。

您可以编写一个简单的函数，如下所示：

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;

}

大多数情况下，这对于您的应用程序来说是足够有效的。如果您正在实现平方根或其他超越函数，那么您将不得不考虑优化。

此外，一些处理器针对任意整数幂进行了优化，GPU当然也是如此(尽管这并没有太大帮助，除非这是一篇与图形相关的文章，并且没有这样的标签)。

希望这能回答您的问题:)

Answer 3

你有没有尝试过tommath (不确定它是否符合你的性能要求)？它的多精度整数算法库！