add a quotien_and_rem_euclid method to Euclid trait

[tdelabro]

Sometimes you need both the quotient and the remainder.

With the current state of the trait you would have to call both div_euclid and rem_euclid. But part of the computation done by each one of those methods can be shared. See:

impl Euclid for f32 {
    #[inline]
    fn div_euclid(&self, v: &f32) -> f32 {
        let q = <f32 as crate::float::FloatCore>::trunc(self / v);
        if self % v < 0.0 {
            return if *v > 0.0 { q - 1.0 } else { q + 1.0 };
        }
        q
    }

    #[inline]
    fn rem_euclid(&self, v: &f32) -> f32 {
        let r = self % v;
        if r < 0.0 {
            r + <f32 as crate::float::FloatCore>::abs(*v)
        } else {
            r
        }
    }
}

can become

#[inline]
    fn div_and_rem_euclid(&self, v: &f32) -> (f32, f32) {
        let q = <f32 as crate::float::FloatCore>::trunc(self / v); 
        let r = self % v;
        if r < 0.0 {
            (if *v > 0.0 { q - 1.0 } else { q + 1.0 }, r + <f32 as crate::float::FloatCore>::abs(*v))
        } else {
            (q, r)
        }
    }

And you spare one computation of self % v. This is a really small optimization for f32, but with the kind of big field elements I'm working with, it actually a pretty significant hit. The method can be defined with a default impl:

fn div_and_rem_euclid(&self, v: &f32) -> (f32, f32) {
        (self.div_euclid(), self.rem_euclid())
}

Which has not optimization nor drawback for people using it, but can be overwritten in order to achieve better performances.

Wdyt?

[cuviper]

Sure, we can add a defaulted method to Euclid, and I supposed CheckedEuclid too while we're at it. For primitive types, I expect the difference will usually get optimized away, but for types like BigInt it could definitely improve performance to use a combined method.

[dragomang87]

Doesn't this highlight a conceptual problem with the default implementation? It seems to me that it would be more natural to require div_and_rem_euclid and provide div_euclid and rem_euclid instead

[cuviper]

Perhaps, but it would be a breaking change to flip that. BigInt still has good reason to implement both combined and separately -- avoiding extra division when combined, and avoiding extra fixups when separate.