Rust specializing math operations per type

[lucaszanella]

One very easy way to take the addition modulo of 2 numbers is to cast them to u128 like this, so I avoid overflow and implement it for all unsigned integers u8, u16, u32, u64:

pub fn modulo_add<T: Into<u64>, U: Into<u64>, M: Into<u64>>(t: T, u: T, m: M) -> u64{
    ((t.into() as u128 + u.into() as u128) % m.into() as u128) as u64
}

What if I wanted to be REALLY generic over the types being moduled out? Not only for unsigned integers convertible to u64 but any type?

Well, of course I could do this:

pub fn modulo_add<T: core::ops::Add<Output=M>, U, M: core::ops::Rem<Output=M> + TryInto<R>, R>(t: T, u: T, m: M) -> R{
    ((t+u)%m).try_into().ok().unwrap()
}

but now I'm not avoiding overflow, because if T=U=u64, then adding u64::MAX with u64::MAX would give overflow and thus the mod would not work.

Ideally on C++ I'd implement the addition for u8 and make it cast to u16, and the u16 to cast to u32, and u64 to u128, but on Rust you cannot have specialization of functions for each type.

Also, maybe I have a really fast hardware implementation for u64 only. Or I want to do it differently depending on the type.

What would be a good solution here?

[scottmcm]

@lucaszanella

What if I wanted to be REALLY generic over the types being moduled out?

Well, in general you'd make a trait method just for modular addition, because for a BigInteger, doing the full addition then the modulo is suboptimal. (Less so for addition, TBH, but obviously critical for modular exponentiation.)

Then typically you'd use a macro to implement your trait for all the primitive integer types -- here's num_traits doing that, for example: num-traits/sign.rs at 96a89e63258762d51f80ec141fcdf88d481d8dde · rust-num/num-traits · GitHub