optimisation des calculs arithmétiques modulaires en C++

Question

Je développe un code d'algèbre linéaire qui est modélisé sur le type de coefficient de matrice . L'un des types possibles est une classe pour faire arithmétique modulaire, naïvement mis en œuvre comme suit:

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

Cependant, lorsque le programme fonctionne avec les Modular<int> coefficients, il est plusieurs fois plus lent que lorsqu'il fonctionne avec int coefficients .

Quelles sont les choses que je devrais changer dans la classe "Modulaire" dans afin d'obtenir des performances maximales?

Par exemple, il est possible d'optimiser les expressions comme a*b + c*d à (a.val_*b.val_ + c.val_*d.val_) % modulus, et au lieu de la obvious:

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

Answer 1

Oui. C'est possible. Ce que vous voulez rechercher est "modèles d'expression" et commencer à partir de là. A partir de là, vous allez devoir construire une logique de métaprogrammes pour optimiser/simplifier l'expression. Loin d'une tâche triviale, mais ce n'est pas ce que vous avez demandé.

NVM - il est trivial façon:

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(); 
} 

Si vous étiez intelligent bien, vous mettiez l'utilisation de% dans le constructeur pour modulaire il est donc toujours modulaire; vous devez également mettre en place des vérifications pour vous assurer que LH et RH sont compatibles avec la merde SFINAE pour empêcher les opérateurs de les tuer à tout moment. Vous pouvez également faire de module un paramètre de modèle et fournir des métafonctions pour y accéder. En tout cas ... vous y allez. Editer: BTW, vous pouvez utiliser cette même technique pour faire vos matrices calculer plus rapidement.Au lieu de créer une nouvelle matrice pour chaque opération dans une chaîne d'opérations, vous faites ces choses et finalement faites le calcul, élément par élément, lorsque vous affectez le résultat. Il y a des articles sur Internet et tout, en comparaison avec FORTRAN et autres. A été l'une des premières utilisations de la métaprogrammation comme l'utilisation de modèles en C++. Aussi dans le livre http://www.amazon.com/Scientific-Engineering-Introduction-Advanced-Techniques/dp/0201533936 < - gardez à l'esprit cependant que "techniques avancées" était dans 94: p. Ce n'est pas aussi pertinent aujourd'hui.

Answer 2

est Modulus distributive sur l'addition. Par conséquent A% N + B% N == (A + B)% N

En ce qui concerne l'opérande ou le module négatif, la dernière fois que j'ai vérifié le standard C++ laisse le résultat à la discrétion du vendeur. Donc, ce qui précède pourrait ne pas fonctionner avec des négatifs.

Answer 3

Je ne peux pas dire avec certitude sans savoir à quoi sert la bibliothèque, mais il me semble que c'est probablement trop bas niveau.

Puisque vous vous souciez de la performance, je suppose que vos matrices sont assez grandes. Cela signifie que vous allez probablement voir des gains de vitesse beaucoup plus importants en utilisant des algorithmes plus rapides que d'essayer d'optimiser des choses comme ça. Les coefficients int seront probablement plus rapides, peu importe ce que vous faites.

Même si vous enregistrez quelques mod-opérations, l'accélération sera seulement par un facteur constant et probablement moins de 10x. L'optimisation pour le cache pourrait probablement vous donner plus que cela pour la plupart des opérations matricielles.

Mon conseil est de profiler pour voir quelles opérations sont trop lentes puis google cette opération et de regarder quels algorithmes existent (par exemple le Strassen algorithm pour la multiplication). Vous devriez être conscient de la taille de vos matrices et si elles sont clairsemées ou denses.

Dans tous les cas, si vous devez vous renseigner à propos de ce genre de choses, il vaut probablement mieux utiliser une bibliothèque existante.