2
\$\begingroup\$

A \$Z^m\$ number system includes integers in the interval \$[0, m)\$ when \$m > 0\$ or \$(m, 0]\$ when \$m < 0\$. The code defines a trait Mod to represent numbers in this system and the +, -, and * operator for it.

use std::ops::Add;
use std::ops::Mul;
use std::ops::Sub;

struct Mod<T: Modulo<T>> {
    modulo: T,
    i: T,
}

trait Modulo<T> {
    fn modulo(&self, n: T) -> T;
}

impl Modulo<i32> for i32 {
    fn modulo(&self, n: i32) -> i32 {
        let mut x: i32 = *self;
        while x.signum() != n.signum() {
            x += n;
        }
        x % n
    }
}

impl Mod<i32> {
    fn new(modulo: i32, i: i32) -> Mod<i32> {
        let n = i.modulo(modulo);
        Mod {
            modulo: modulo,
            i: n,
        }
    }
}

impl Add for Mod<i32> {
    type Output = Mod<i32>;
    fn add(self, other: Mod<i32>) -> Mod<i32> {
        Mod::new(self.modulo, self.i + other.i)
    }
}

impl Sub for Mod<i32> {
    type Output = Mod<i32>;
    fn sub(self, other: Mod<i32>) -> Mod<i32> {
        Mod::new(self.modulo, self.i - other.i)
    }
}

impl Mul for Mod<i32> {
    type Output = Mod<i32>;
    fn mul(self, other: Mod<i32>) -> Mod<i32> {
        Mod::new(self.modulo, self.i * other.i)
    }
}

fn main() {
    let x = Mod::new(-5, 3);
    let y = Mod::new(-5, 8);
    println!("{}", (x + y).i);
    let x = Mod::new(-5, 3);
    let y = Mod::new(-5, 8);
    println!("{}", (x - y).i);
    let x = Mod::new(-5, 3);
    let y = Mod::new(-5, 8);
    println!("{}", (x * y).i);
}

All suggestions are welcome, but I am particularly interested in:

  • Extending to u32, u16, u8, i16, i8 etc without too much code duplication.
  • Increasing performance.
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

I would hesitate to implement Mod<T> * Mod<T>, and instead implement Mod<T> * T (and vice-versa). This is because you make no attempt to preserve the rhs' modulo, so you probably shouldn't have one there.

Consider the code

let mut x: i32 = *self;
while x.signum() != n.signum() {
    x += n;
}
x % n

That while loop makes this operation \$\mathcal{O}(n)\$, whereas a simpler implementation

((x % n) + n) % n

is \$\mathcal{O}(1)\$.

Performance elsewhere is probably uninteresting, since it devolves to basic integer operations.

Extending to other T should probably be done by being generic over the Mod and Add traits, as well as whatever particular operation is needed to implement. Something like

impl<T> Sub<T> for Mod<T>
    where T: Add<T> + Mod<T> + Sub<T>
{
    type Output = Mod<T>;
    fn sub(self, other: T) -> Mod<T> {
        Mod::new(self.modulo, self.i - i)
    }
}

The Add and Mod are needed by Mod::new, the Sub is needed inside the sub call.

\$\endgroup\$
3
  • \$\begingroup\$ Wouldn't (x % n) + n suffice? \$\endgroup\$
    – qed
    Sep 15, 2016 at 18:59
  • \$\begingroup\$ Actually it has to be ((x % n) + n) % n, I don't quite understand why, thought. \$\endgroup\$
    – qed
    Sep 15, 2016 at 19:46
  • \$\begingroup\$ Rust's % corresponds to remainder, not modulus. stackoverflow.com/a/13683709/1763356 \$\endgroup\$
    – Veedrac
    Sep 15, 2016 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.