多次指数运算实现

Question

有没有人知道已经实现的多指数算法？我正在寻找一些使用快速算法计算给定向量A、B的乘积A[i]^B[i]的方法。

谢谢！

- zif

---

这似乎还不错 - 如果是基于图形的话，甚至可以通过GPU更快地完成。 - Michael Dorgan

请指明您拥有哪种数据类型：浮点数或大整数。在这两种情况下，计算prod(a_i^b_i)的方式非常不同。 - Alexandre C.

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算法（或者自己编写一个）。

- Alexandre C.

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当然也是如此（尽管这对于非图形相关帖子并没有太大帮助，而且未被标记为此类帖子）。

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

- Thomas Russell

---

if语句在很多方面都是不好的 :) 它不仅检查了一些错误的条件（可能是大小），而且试图返回而不是抛出异常，并且在函数具有非void返回类型时尝试返回空值。考虑将其删除，毕竟这只是一个示例代码。 - unkulunkulu

哦，是的，我的意思是vec1.length() != vec2.length()，谢谢 :) 我已经将其更改为断言，:) - Thomas Russell

@Shaktal：即使是断言也需要分号。 - TonyK

我认为zif不是在寻找向量指数，而是要求指数的乘积（即结果是标量）。这是一种常见的加密操作，因此他可能希望对大整数进行操作，而不是浮点数据。@zif：你能澄清一下吗？ - Stephen Canon

Stephen是正确的。我希望有人已经在某个库中实现了类似Pippenger算法（或类似算法）的东西。 - zif

Answer 3

你尝试过 tommath 吗（不确定它是否符合你的性能要求）？它是一个多精度整数算术库！

- rru