# Z^m number system in Rust

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

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.

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.

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