在C++中优化模算术计算

Question

我正在开发一些线性代数代码，它是以矩阵系数类型为模板的。一种可能的类型是执行模算术的类，简单地实现如下：

template<typename val_t> // `val_t` is an integer type
class Modular 
{
  val_t val_;
  static val_t modulus_;
public:
  Modular(const val_t& value) : val_(value) { };
  static void global_set_modulus(const val_t& modulus) { modulus_ = modulus; };

  Modular<val_t>& operator=(const Modular<val_t>& other) { val_ = other.val_; return *this; }

  Modular<val_t>& operator+=(const Modular<val_t>& other) { val_ += other.val_; val_ %= modulus_; return *this; }
  Modular<val_t>& operator-=(const Modular<val_t>& other) { val_ -= other.val_; val_ %= modulus_; return *this; }
  Modular<val_t>& operator*=(const Modular<val_t>& other) { val_ *= other.val_; val_ %= modulus_; return *this; }
  Modular<val_t>& operator/=(const Modular<val_t>& other) { val_ *= other.inverse().val_; val_ %= modulus_; return *this; }

  friend Modular<val_t> operator+(const Modular<val_t>& a, const Modular<val_t>& b) { return Modular<val_t>((a.val_ + b.val_) % Modular<val_t>::modulus_); };
  friend Modular<val_t> operator-(const Modular<val_t>& a, const Modular<val_t>& b) { return Modular<val_t>((a.val_ - b.val_) % Modular<val_t>::modulus_); };
  // ...etc.
};

但是，当程序使用Modular<int>系数运行时，它比使用int系数运行时慢几倍。

为了获得最大的性能，我应该在"Modular“类中更改哪些内容？

例如，是否可以将像a*b + c*d这样的表达式优化为(a.val_*b.val_ + c.val_*d.val_) % modulus，而不是obvious

(((a.val_*b.val_) % modulus) + ((c.val_*d.val_ % modulus) % modulus) % modulus)

Answer 1

是。这是可能的。你要查找的是“表达式模板”，并从那里开始。在这一点上，您将不得不构建一些元程序逻辑来优化/简化表达式。这不是一项微不足道的任务，但这不是您所要求的。

NVM -这很简单：

int count = 0;
int modulus() { count++; return 10; }

template < typename T >
struct modular
{
  modular(T v) : value_(v) {}

  T value() const { return value_; }
  void value(T v) { value_ = v; }

  typedef modular<T> modular_type;
  typedef T raw_type;
private:
  T value_;
};

template < typename LH, typename RH >
struct multiply
{
  multiply(LH l, RH r) : lh(l), rh(r) {}

  typedef typename LH::modular_type modular_type;
  typedef typename LH::raw_type raw_type;

  raw_type value() const { return lh.value() * rh.value(); }

  operator modular_type () const { return modular_type(value() % modulus()); }

private:
  LH lh; RH rh;
};

template < typename LH, typename RH >
struct add
{
  add(LH l, RH r) : lh(l), rh(r) {}

  typedef typename LH::modular_type modular_type;
  typedef typename LH::raw_type raw_type;

  raw_type value() const { return lh.value() + rh.value(); }
  operator modular_type () const { return modular_type(value() % modulus()); }

private:
  LH lh; RH rh;
};

template < typename LH, typename RH >
add<LH,RH> operator+(LH const& lh, RH const& rh)
{
  return add<LH,RH>(lh,rh);
}

template < typename LH, typename RH >
multiply<LH,RH> operator*(LH const& lh, RH const& rh)
{
  return multiply<LH,RH>(lh,rh);
}

#include <iostream>

int main()
{
  modular<int> a = 5;
  modular<int> b = 7;
  modular<int> c = 3;
  modular<int> d = 8;

  std::cout << (5*7+3*8) % 10 << std::endl;

  modular<int> result = a * b + c * d;
  std::cout << result.value() << std::endl;

  std::cout << count << std::endl;

  std::cin.get();
}

如果你聪明的话，你应该在模块化的构造函数中使用%，这样它就总是模块化的；你还应该检查以确保LH和RH与SFINAE垃圾兼容，以防止操作符在任何时候杀死它。您还可以将模数设置为模板参数，并提供元函数来访问它。在任何rate...there你都可以去。

编辑:顺便说一句，你可以使用同样的技术让你的矩阵计算得更快。不是为一串操作中的每个操作创建新的矩阵，而是进行这些操作，然后在分配结果时，逐个元素地进行数学运算。在互联网上有很多关于它的论文，把它和FORTRAN之类的东西做比较。是元编程的最早用法之一，就像在C++中使用模板一样。同样在http://www.amazon.com/Scientific-Engineering-Introduction-Advanced-Techniques/dp/0201533936 <一书中，请记住，“高级技术”在94 :p中。它在今天已经不那么重要了。

Answer 2

模数在加法上是分布的。因此A%N+B%N == (A + B) %N

关于负操作数或模数，上次我检查C++标准时，将结果留给供应商自行决定。因此，上面的方法可能不适用于负片。

Answer 3

如果不知道这个库是用来做什么的，我就不能确定，但在我看来，这个级别可能太低了。

由于您担心性能，因此我假设您的矩阵非常大。这意味着，使用更快的算法可能会比尝试优化这样的东西获得更大的速度增益。无论您做什么，int系数都可能会更快。

即使你节省了一些mod操作，加速也只会是一个恒定的因子，而且可能不到10倍。对于大多数矩阵运算，针对缓存进行优化可能会为您提供更多。

我的建议是分析一下哪些操作太慢，然后谷歌那个操作，看看有什么算法(例如乘法的Strassen algorithm )。你应该知道你的矩阵有多大，它们是稀疏的还是密集的。

在任何情况下，如果你必须询问这些东西，你可能会更好地使用现有的库。