C++でモジュラ演算を最適化する

Question

行列係数型でテンプレート化された線形代数コードをいくつか開発しています。可能なタイプの一つは、次のように単純に実装され、 剰余演算を行うためのクラスです：プログラムはModular<int>係数で実行する場合しかし、それはint係数を実行したときに比べて数 倍遅い

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. 
}; 

。

最高のパフォーマンスを得るために、 オーダーの「モジュラー」クラスで変更する必要があるものは何ですか？

(((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のクラップスと互換性があることを確認して、オペレーターがいつでもそれを殺さないようにするためにチェックインすることもできます。モジュラスをテンプレート・パラメーターにして、それにアクセスするためのメタ機能を提供することもできます。とにかく...そこに行く。

編集：BTWでは、この同じ手法を使用して行列を高速に計算できます。演算の文字列で各演算のための新しい行列を作成するのではなく、結果を代入するときにこれらのことを行い、最終的に要素ごとに計算を行います。インターネット上の記事や、FORTRANなどと比較した記事があります。 C++でのテンプレート使用のようなメタプログラミングの最初の使用の1つでした。また、本の中でhttp://www.amazon.com/Scientific-Engineering-Introduction-Advanced-Techniques/dp/0201533936 < - 「高度な技術」は94：pにありました。今日はそれほど関連性がありません。

Answer 2

モジュラス添加にわたって分配がある：例えば

は、それが可能であり、代わりobviousの、(a.val_*b.val_ + c.val_*d.val_) % modulusにa*b + c*d のような式を最適化することです。したがって、負のオペランドまたはモジュラスに関しては、C++標準をチェックした最後の時間はベンダーの裁量に任せました。したがって、上記はネガティブでは機能しない可能性があります。

Answer 3

ライブラリが何であるかわからないとわからないけど、これはおそらく低すぎるようです。

パフォーマンスが心配なので、私はあなたの行列がかなり大きいと仮定します。つまり、このようなものを最適化しようとするよりも高速のアルゴリズムを使用することで、はるかに大きな速度向上が見られるでしょう。 intの係数は、あなたが何をしていようと、おそらくより速いでしょう。

いくつかのモジュレーション演算を保存しても、スピードアップは一定の係数だけで、たぶん10x未満です。キャッシュを最適化すると、ほとんどのマトリックス操作でこれ以上の効果が得られます。

私のアドバイスは、どの操作が遅すぎるのかを調べて、その操作をGoogleに案内し、どのアルゴリズムが存在するかを調べることです（例：Strassen algorithm、乗算用）。あなたの行列がどれほど大きいのか、それらがまばらか密なのかを知っておくべきです。

いずれにしても、このことについて質問する必要がある場合は、とにかく既存のライブラリを使用する方がよいでしょう。