Многоэкспоненциальная реализация

Question

Кто-нибудь знает о реализованном алгоритме мульти-возведения в степень?Я ищу то, что с учетом векторов A, B вычислило бы произведение A [i] ^ B [i] с использованием некоторых быстрых алгоритмов.

Спасибо!

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 вместо того, чтобы писать цикл самостоятельно, дает то преимущество, что , когда вы знаете, что производительность является проблемой , вы можете заменить алгоритм inner_product алгоритмом parallel_inner_product, предоставленным третьим -партийная библиотека (или напишите ее самостоятельно).

Answer 2

Вы пробовали Tommath (не уверены, что он соответствует вашим требованиям к производительности)? Его целочисленная арифметическая библиотека с высокой точностью!

Answer 3

Как быстро это должно быть?В зависимости от размера вашего алгоритма, функция мощности не должна быть слишком узким местом.

Вы могли бы написать простую функцию, такую ​​как следующее:

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;

}

Большинство израз это будет достаточно эффективно для вашего приложения.Если бы вы внедрили квадратный корень или какую-то другую трансцендентную функцию, вы бы тоже взглянули на оптимизацию.

Кроме того, некоторые процессоры оптимизированы для произвольных интегральных степеней, и графические процессоры, безусловно, таковы (хотя это не сильно поможет, еслиЭто пост, связанный с графикой, и он не помечен как таковой).

Надеюсь, что это ответ на ваш вопрос:)