div_rem methods / DivRem trait

[clarfonthey]

Implementation A (less likely)

This would be nice for computations that require doing both operations simultaneously. Crates like ramp currently implement div_rem methods because they might be expensive, and it'd be nice if we could get this sort of trait in the standard library so that generic code could request DivRem instead of just Div + Rem.

Additionally, when impl specialisation comes along, we can offer a blanket implementation given Div and Rem, then allow downstream implementers to specialise.

Implementation B (more likely)

All of the libstd types could offer div_rem, checked_div_rem, etc. methods that can then be combined into a DivRem trait from a crate like num.

[ticki]

The standard library provides no bigint or the alike, and I fail to see the purpose as you rarely use more than one bigint library, so there's no environment to "unify".

For primitive integer types, these are two instructions no matter what. AFAIK no major architectures provide acceleration for this rare usecase. Even if they did, it would be better left for LLVM to optimize.

[clarfonthey]

The standard library provides no bigint or the alike, and I fail to see the purpose as you rarely use more than one bigint library, so there's no environment to "unify".

Generic mathematical code doesn't necessarily bias toward any particular bigint library, although I do see an argument toward just using the num crate for this type of trait, because it is a commonly accepted library for these sorts of traits. I was suggesting it because the maintenance burden is rather low if it's included in the standard library, and the trait is very unlikely to change too.

For primitive integer types, these are two instructions no matter what. AFAIK no major architectures provide acceleration for this rare usecase. Even if they did, it would be better left for LLVM to optimize.

That's not quite true. Pipelined architectures will merge div and mod instructions together so that they require one div/mod computation instead of two. Granted, a majority of the time the pipeline will be able to find instructions that can be run while both computations are running, meaning that there's no slowdown for the end user, but this isn't the case if you have to do a lot of div/mod computations.

[ticki]

Generic mathematical code doesn't necessarily bias toward any particular bigint library, although I do see an argument toward just using the num crate for this type of trait, because it is a commonly accepted library for these sorts of traits. I was suggesting it because the maintenance burden is rather low if it's included in the standard library, and the trait is very unlikely to change too.

You misunderstood me. There are certain requirements for something to deserve a place in the standard library:

It either must be a common usecase (which this arguably isn't), or it must unify a divided ecosystem (which this against doesn't, as it is really too rare). Without a proper strong argument for adding it, it won't pass.

That's not quite true. Pipelined architectures will merge div and mod instructions together so that they require one div/mod computation instead of two. Granted, a majority of the time the pipeline will be able to find instructions that can be run while both computations are running, meaning that there's no slowdown for the end user, but this isn't the case if you have to do a lot of div/mod computations.

Oh, I'm aware of that, but that isn't an acceleration, that's just a hw optimization. By acceleration, I meant a standalone instruction for this. Then again, it is none of rustc's business. It's better left to llvm.

[comex]

For primitive integer types, these are two instructions no matter what. AFAIK no major architectures provide acceleration for this rare usecase. Even if they did, it would be better left for LLVM to optimize.

x86 does:

"Signed divide EDX:EAX by r/m32, with result stored in EAX = Quotient, EDX = Remainder."

(But as you say, this is something that's easy for LLVM to optimize.)

[ticki]

Oh, nice. Didn't know that instruction. But I bet my arm that LLVM already optimizes this. It should fall straight during peephole optimization stage.

[tueda]

I admit this is a rare case, but I hit this issue when I consider a possibility to have a library for polynomial rings in Rust. The coefficient type of polynomials can be, for example, either one of primitive integer types, big integers (num_bigint or ramp), possibly some new types for finite fields or quotient fields, or a polynomial ring itself for recursive structure of multivariate polynomials. The user can choose one of them. Definitely div and rem are expensive for big integers and polynomials. (Well, the exact meaning of div/rem would be a good question and may depend on libraries.) Separating them probably causes double work; I don't think the compiler can optimize them into one "div_rem" operation in general.

Actually, both num_bigint::BigInt and ramp::Int have div_rem of the num_integer::Integer trait, but I would hesitate to have polynomial types implementing Integer trait; apparently polynomials are not integers. So in this sense for now there is no common place of div_rem for objects more general than integers.

Maybe a new DivRem trait should be put as an external crate in Crates.io, with saying "When some types in your library implement both std::ops::Div and std::ops::Rem, please import this crate and implement the trait, if you want to provide the maximum performance to users." But I'm not sure that such a situation is so natural; library developers should implement std::ops::Div and std::ops::Rem in the standard library, and also DivRem in an external library, though they are so similar operations.

[programmerjake]

I'm currently implementing polynomials as part of my algebraic number library, having a well-known DivRem trait would be useful.

[gilescope]

Is it that rare that you want to do both? I've seen a few times where it would have been handy.

[gilescope]

Today for example it would have come in handy on a std lib pr I was writing. In fact I would probably be happy enough if it was just available for writing the std lib as that’s where efficiency is most needed.

[clarfonthey]

For what it's worth, given the precedent in libstd, it would probably make the most sense to have a bunch of div_rem, checked_div_rem, etc. methods, rather than a trait.

[k3d3]

I'd have to agree that div_mod or div_rem would be useful in stdlib. I've definitely found myself reaching for a divmod crate more than once.