当前位置：文江博客话题详情

多重幂运算的实现

发布于 2024-11-26 08:52:55 字数 81 浏览 4 评论 0原文

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

谢谢！

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

我不会写诗 2024-12-03 08:52:55

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

干净的数值方法当然是先取对数。事实上，即使结果是有限的，部分乘积也很容易下溢/溢出。

惯用的相应 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 而不是自己编写循环的优点是，一旦您知道性能是一个问题，您就可以替换 inner_product 算法与第三方库提供的 parallel_inner_product 算法（或自己编写一个）。

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

回复收藏 0 原文

另类 2024-12-03 08:52:55

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

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

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 也确实如此（尽管这没有多大帮助，除非这是一篇与图形相关的文章，并且没有这样标记）。

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

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

回复收藏 0 原文