Comment puis-je exiger qu'une référence à un type générique puisse être comparée pour l'égalité par rapport au type générique?

Question

J'essaye de mettre en application un algorithme qui repose sur l'exponentiation modulaire. Je ne pouvais pas trouver de construction d'exponentiation modulaire pour les types natifs comme u64 (uniquement pour les bigints), donc j'ai pensé que je coderais un standard modular exponentiation by repeated squaring method.

Voici ce que je suis venu avec:

fn powm(base: &u64, exponent: &u64, modulus: &u64) -> u64 { 
    if *modulus == 1u64 { 
     0 
    } else { 
     let mut result = 1; 
     let mut base = self % modulus; 
     let mut exp = *exponent; 
     while exp > 0 { 
      if exp % 2 == 1 { 
       result = (result * base) % modulus; 
      } 
      exp >>= 1; 
      base = (base * base) % modulus; 
     } 
     result 
    } 
} 

Cela fonctionne très bien. Maintenant, je voudrais rendre cette fonction générique afin qu'elle fonctionne également pour les types numériques autres que u64. C'est là que je commence à me perdre un peu.

J'ai trouvé la caisse num, qui a un trait Num qui spécifie les opérations numériques de base. Après avoir séparé un nouveau PowM trait et la création d'un groupe de bornes de trait, je me retrouve avec:

extern crate num; 

use num::Num; 
use std::ops::{ShrAssign,Rem}; 

pub trait PowM { 
    fn powm(&self, exponent: &Self, modulus: &Self) -> Self; 
} 

pub trait Two { 
    fn two() -> Self; 
} 

impl Two for u64 { 
    fn two() -> u64 { return 2u64 } 
} 

impl Two for usize { 
    fn two() -> usize { return 2usize } 
} 

impl<T> PowM for T 
    where T: Num + Two + ShrAssign<T> + Rem<T> + PartialOrd<T> { 
    fn powm(&self, exponent: &T, modulus: &T) -> T { 
     if modulus == T::one() { 
      T::zero() 
     } else { 
      let mut result = T::one(); 
      let mut base = *self % *modulus; 
      let mut exp = *exponent; 
      while exp > T::zero() { 
       if exp % T::two() == T::one() { 
        result = (result * base) % *modulus; 
       } 
       exp >>= T::one(); 
       base = (base * base) % *modulus; 
      } 
      result 
     } 
    } 
} 

La seule plainte, le compilateur donne est le suivant

error[E0277]: the trait bound `&T: std::cmp::PartialEq<T>` is not satisfied 
    | 
30 |   if modulus == T::one() { 
    |     ^^ can't compare `&T` with `T` 
    | 
    = help: the trait `std::cmp::PartialEq<T>` is not implemented for `&T` 
    = help: consider adding a `where &T: std::cmp::PartialEq<T>` bound 

Je suis en train d'ajouter le trait limites, mais finissent par courir après beaucoup d'erreurs de compilation sur la durée de vie que je ne comprends pas complètement, et finissent coincé avec les éléments suivants:

impl<'a, T> PowM for T 
    where T: 'a + Num + Two + ShrAssign<T> + Rem<T> + PartialOrd<T>, 
      &'a T: PartialEq<T> { 
    fn powm(&self, exponent: &T, modulus: &T) -> T { 
     if modulus == T::one() { 
[...] 

qui donne encore des erreurs. Comment puis-je réparer ça?

Answer 1

Vous pouvez ignorer le problème et comparer une référence à une référence ou non référence à un non-référence:

if modulus == &T::one() { 
// Or 
if *modulus == T::one() { 

Ou vous pouvez utiliser trait mieux classé limites du terrain:

impl<T> PowM for T 
where 
    T: Num + Two + ShrAssign<T> + Rem<T> + PartialOrd<T>, 
    for <'a> &'a T: PartialEq<T>, 
{ 
    // ... 
} 

Dans les deux cas, vous devez exiger que T implémente Copy ou implémente Clone, puis ajoute les appels appropriés au .clone().

Voir aussi:

• How does for<> syntax differ from a regular lifetime bound?