Add wide division method(s) to (unsigned) integer types

[gendx]

Proposal

Problem statement

Several helper methods have been added and/or stabilized to help implement addition and multiplication on big integer types (rust-lang/rust#85532). An extension of that is implementing division on big integers, which requires another building block: a wide division function (which can be seen as the reverse of widening_mul):

// Returns (quotient, remainer) of the division of `(high << 64 | low)` by `divisor`.
// This assumes that the quotient fits into a u64 (the remainder always fits as the divisor is a `u64`).
fn wide_div(high: u64, low: u64, divisor: u64) -> (u64, u64);

Contrary to the naive division on u128 (which is typically implemented by the __udivmodti4 compiler built-in, see also rust-lang/rust#44545):

fn divmod_u128(wide: u128, divisor: u128) -> (u128, u128) {
    (wide / divisor, wide % divisor)
}

...this wide_div can be more efficient:

• the divisor is only 64 bits rather than an arbitrary 128-bit,
• the quotient is assumed (by the caller) to fit in only 64 bits,
• importantly, on x86(_64) architectures, the DIV instruction already implements wide_div.

The same wide_div API could be offered on all unsigned integer types up to u64, as well as usize.

Motivating examples or use cases

This API is a useful building block in several contexts:

• Implementing division on big integers, e.g. https://docs.rs/num-bigint/0.4.6/src/num_bigint/biguint/division.rs.html#100 and https://docs.rs/num-bigint/0.4.6/src/num_bigint/biguint/division.rs.html#294
• Generating magic constants for fast dividers (see libdivide, ported to a crate), e.g. https://github.com/ridiculousfish/libdivide/blob/v5.3.0/libdivide.h#L513-L636, https://docs.rs/libdivide/0.4.1/src/libdivide/lib.rs.html#422-424

Solution sketch

For all u8, u16, u32, u64, usize:

impl uN {
    // Returns (quotient, remainer) of the division (high << uN::BITS | low) by divisor.
    fn wide_div(high: uN, low: uN, divisor: uN) -> (uN, uN);
}

Default implementation:

impl u64 {
    fn wide_div(high: u64, low: u64, divisor: u64) -> (u64, u64) {
        // TBD: should invalid inputs cause a panic? arbitrary results? undefined behavior?
        debug_assert!(high < divisor);

        let a = ((high as u128) << 64) | (low as u128);
        let b = divisor as u128;
        ((a / b) as u64, (a % b) as u64)
    }
}

Optimized implementation:

• DIV instruction on x86 variants,
• Manually unrolled code might be more efficient/succinct than the __udivmodti4 built-in on other platforms, e.g. https://github.com/ridiculousfish/libdivide/blob/v5.3.0/libdivide.h#L554-L634.

Open questions

• Have a separate unsafe wide_div_unchecked() variant, when the caller asserts that the quotient will fit in a uN?
• Also implement on signed integer types (e.g. to mirror the IDIV instruction on Intel)? Would that be useful? Should the low input be unsigned (as with iN::widening_mul)?
• Naming? Order of the low & high parameters?

Alternatives

This could be implemented manually (as is indeed done in the num_bigint crate). However, this requires:

1. special-casing CPU architectures (currently x86 and x86_64) to obtain the best performance - which could be a maintenance concern,
2. unsafe code to emit the ideal div instruction on x86(_64),
3. dispatch code to other integer types for the case of usize,
4. carefully written code to avoid the default LLVM calls (__udivti3, __umodti3 or __udivmodti4) which may not be ideal (128-bit integer division with remainder is not combined to a single operation rust#44545), e.g. https://github.com/ridiculousfish/libdivide/blob/v5.3.0/libdivide.h#L554-L634.

Having such methods directly on integer types in the standard library could therefore be helpful and more maintainable for the wider ecosystem, similarly to other bigint helper methods (rust-lang/rust#85532).

Links and related work

• Prior art in the num_bigint crate: https://docs.rs/num-bigint/0.4.6/src/num_bigint/biguint/division.rs.html
• Prior art in libdivide: https://github.com/ridiculousfish/libdivide/blob/v5.3.0/libdivide.h#L513-L636
• https://stackoverflow.com/questions/73667228/128bit-by-64bit-native-division

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[pitaj]

I would call it narrowing_div, and I think it would make sense to have checked, unchecked, and strict variants.

[cuviper]

See also #774 for non-wide div_rem.

It would be really nice if we could do this with help from the backend (LLVM), so it can handle the target optimizations, transformations of const divisors, etc. That may also allow 256-by-128 division.

the quotient is assumed (by the caller) to fit in only 64 bits,

For x86 DIV it's a hardware exception if you fail this, same as dividing by zero, so we would need to check this by default. In num-bigint's function, we assert hi < divisor in debug only, because we expect all the self-contained callers should be ok.

[programmerjake]

I think these methods should be implemented for all integer types for consistency. Eventually, I think we should just generate LLVM 128 or 256-bit integer division operations (like we do with u128::carrying_mul which generates a 256-bit multiplication) and LLVM will optimize those to the appropriate division instructions. However, LLVM doesn't currently do that properly (though someone's apparently working on that since March).

[kennytm]

Implementation of __udivmodti4 already has a special branch handling the divisor.hi == 0 && numerator.hi < divisor.lo case, bringing up the "efficiency" argument against #774 is counter-effective. Being a "basic building block" is good enough.

Regardless, this function should be named widening_div_rem (or narrowing_div_rem) since this function returns both quotient and remainder, not just the quotient.

[programmerjake]

For now we could generate inline assembly but I think normal LLVM IR is eventually what we'll want since that allows LLVM to optimize the division with surrounding code better, sometimes that'll mean LLVM doesn't actually need to generate a division instruction at all (e.g. division by a power of 2, or when the inputs are all constants).

[tgross35]

We could do this via __rust_* libcalls while LLVM support is lacking. @quaternic wrote a rather efficient narrowing_div_rem for use in fmod that would be easy enough to expose for all the int types https://github.com/rust-lang/compiler-builtins/blob/46905e56cd2d3caafac33113f56ffd9eef4fe01d/libm/src/math/support/int_traits/narrowing_div.rs.

(I haven't looked at the codegen vs. what's in the LLVM issue)

[programmerjake]

LLVM can codegen arbitrary-sized divisions, it just does it by using a not-particularly efficient method on >128-bit types, and it uses a libcall instead of a single division instruction for 128-by-64-bit division since it doesn't recognize that as anything other than a general 128-bit division.

[gendx]

Implementation of __udivmodti4 already has a special branch handling the divisor.hi == 0 && numerator.hi < divisor.lo case, bringing up the "efficiency" argument against #774 is counter-effective.

Thanks for the pointer. I had stumbled upon an old version of compiler-rt which didn't have this optimization.

Calling __udivmodti4 may still have (at least in theory) an impact over calling udiv128by64to64 directly, for things like the instruction cache, but I agree that this should be measured in practice to see if efficiency is a practical concern.

Being a "basic building block" is good enough.

Agreed :)

[scottmcm]

// TBD: should invalid inputs cause a panic? arbitrary results? undefined behavior?

I think this is an absolutely critical part of this ACP.

Is there a way something can be phrased with NonZero<_> to make it better? Is a checked version of this ever useful? Would something making a biginteger ever not use the unsafe version if it can't be done fully-safely?

[quaternic]

I don't think NonZero helps, because the precondition is exactly high < divisor, which contains the requirement for divisor != 0 as a special case.

The checked version can be convenient: In Knuth's Algorithm D (for multiprecision division), the corresponding operation is used in a context where only high <= divisor can be assumed, but high == divisor can be special cased. See: libm, num-bigint

[kennytm]

in the compiler_rt implementation, on x86_64 the udiv128by64to64 function directly invokes the div instruction, and when high >= divisor it will throw a "#DE" exception which is same as divide-by-zero.

OTOH the fallback udiv128by64to64default seems to just produce some finite result, including the case which divisor == 0 👀

[nia-e]

This was discussed in the last @rust-lang/libs-api meeting; given that it doesn't seem like this actually uses any faster instructions, we're inclined to reject this at least for now. If this does result in better codegen and there are some numbers or disassembly output to show that, feel free to reopen this and we'll take another look at it. Thanks!