rust - 我如何要求可以比较对泛型类型的引用与泛型类型的相等性？

Question

我正在尝试实现一种依赖于模幂的算法。我找不到像 u64 这样的原生类型的任何模块化求幂构造(仅适用于 bigints)，所以我想我应该编写一个标准的 modular exponentiation by repeated squaring method .

这是我想出的:

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

这很好用。现在，我想使此函数通用，以便它也适用于 u64 以外的数字类型。这是我开始有点迷路的地方。

我找到了 num crate，它有一个 Num 特性来指定基本的数字操作。在分离出一个新的 PowM 特征并创建一堆特征边界之后，我最终得到:

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

编译器给出的唯一提示如下

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

我正在尝试添加特征边界，但最终遇到了很多关于我不完全理解的生命周期的编译器错误，并最终陷入以下困境:

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() {
[...]

仍然会报错。我该如何解决这个问题？

Answer 1

您可以忽略该问题并将引用与引用或非引用与非引用进行比较:

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

或者您可以使用更高级别的特征边界:

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

在任何一种情况下，您都需要要求 T 实现 Copy 或者它实现 Clone，然后添加对 的适当调用.clone().

另见:

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