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 계수와 함께 실행하는 경우보다 몇 배 느린 .

최대 성능을 얻으려면 주문의 "모듈 형"클래스에서 변경해야 할 사항은 무엇입니까?

(((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++에서 템플릿 사용과 같은 메타 프로그래밍의 첫 번째 용도 중 하나였습니다. 또한 책 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). 행렬이 얼마나 큰지, 그리고 행렬이 희박하거나 밀도가 있는지 알고 있어야합니다.

어쨌든이 자료에 대해 질문 할 필요가 있다면 어쨌든 기존 라이브러리를 사용하는 것이 좋습니다.