CODEWITHSUNDEEP
rust
Mark
Mark

Reputation: 1454

How can I require that a reference to a generic type can be compared for equality against the generic type?

I'm trying to implement an algorithm which relies on modular exponentiation. I couldn't find any modular exponentiation construct for native types like u64 (only for bigints), so I figured I'd code a standard modular exponentiation by repeated squaring method.

Here's what I came up with:

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

This works fine. Now, I'd like to make this function generic so that it also works for numeric types other than u64. This is where I start to get a bit lost.

I found the num crate, which has a Num trait that specifies basic numeric operations. After separating out a new PowM trait and creating a bunch of trait bounds, I end up with:

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

The only complaint the compiler gives is the following

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

I'm trying to add the trait bounds, but end up chasing a lot of compiler errors about lifetimes I do not fully understand, and end up stuck with the following:

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

which still gives errors. How do I fix this?

Upvotes: 1

Views: 633

Answers (1)

Shepmaster
Shepmaster

Reputation: 430310

You can either ignore the problem and compare a reference to a reference or non-reference to a non-reference:

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

Or you can use higher-ranked trait bounds:

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

In either case, you need to require that T implements Copy or that it implements Clone and then add appropriate calls to .clone().

See also:

Upvotes: 2

Related Questions