Add divmod support

[kmsquire]

Related discussion in #4427

[quinnj]

This would be great. A few of the date conversion algorithms in Datetime utilize divmod.

[StefanKarpinski]

Technically this should be divrem or fldmod, which are unfortunately less enjoyable names.

[JeffBezanson]

We can implement any and all of those.

[fabianlischka]

Should this be closed, given that divrem is implemented now?
#5738

[JeffBezanson]

We might want divmod or fldmod too, they just won't be as efficient.

[StefanKarpinski]

divrem and fldmod make sense but divmod doesn't. div and rem are naturally paired and fld and mod are naturally paired; div and mod, despite the catchiness of the name divmod, are a fundamentally mismatched operations.

[fabianlischka]

Understood, because they wouldn't fulfil a nice invariant.
I just saw that divrem appears to be implemented as

divrem(x,y) = (div(x,y),rem(x,y))

Question: That does not seem faster than, well, computing the quotient using div, and the remainder using rem, i.e. essentially doing the work twice. Is there any trickery behind the scenes?

If not, it seems trivial to add

fldmod(x,y) = (fld(x,y),mod(x,y))

(Oh, except that there is a divrem implementation for BigInts, calling a gmp function, so that should be faster for BigInts)

[quinnj]

I thought this was originally brought up because LLVM has a special instruction for this?

[StefanKarpinski]

It's actually the opposite – LLVM does not have a special instruction for this but x86 does both with idiv. LLVM is usually clever enough to only do one x86 idiv instruction when one div and rem with the same arguments near each other. Given all the other nonsense we're currently doing before div and rem to handle the possibility of the second argument being zero, however, it may be beneficial to explicitly consolidate that checking when doing both. The code generated for div and rem just makes me want to cry.

[JeffBezanson]

That is correct; the extra checks we need to do seem to prevent LLVM from using a single idiv. If we added our own divrem intrinsic this could probably be solved.

[StefanKarpinski]

Isn't there anything we can do to make div and rem less awful? These operations are so important.

[JeffBezanson]

Yes; lobby for and hope for an x86-div-with-trap intrinsic in LLVM.

[JeffBezanson]

Or we could potentially patch the bit of the LLVM optimizer that replaces undefined div and rem operations with random values.

[quinnj]

The perennial division discussion aside, do we still want fldmod? Otherwise, I don't think there's anything else to keep this open.

[quinnj]

Feel free to reopen if there's anything else desired here.