Add new traits for a faster and type safe Div/Rem

[lcnr]

This issue is based on a different idea which I explored in a now yanked rfc.

Add the following traits to num-bigint:

// I am open for name changes, as I am not perfectly satisfied with the current ones.
pub trait ReducingDiv<RHS> {
    type Output;
    fn reducing_div(self, other: RHS) -> Self::Output;
}

pub trait ReducingRem<RHS> {
    type Output;
    fn reducing_rem(self, other: RHS) -> Self::Output;
}

and add the following implementations:
(uX := u8, u16, u32, u64, u128, usize, iX := i8, i16. i32, i64, i128, isize.)

ReducingDiv<&BigUint> for uX -> uX
ReducingRem<uX> for &BigUint -> uX
ReducingRem<&uX> for &BigUint -> uX
ReducingRem<&BigUint> for uX -> uX
ReducingDiv<&BigInt> for iX -> iX
ReducingRem<iX> for &BigInt -> iX
ReducingRem<&iX> for &BigInt -> iX
ReducingRem<&BigInt> for iX -> iX

This is sound as |a| >= |a % b| < |b| and |a / b| <= |a| is always true for integer values.

Motivation

• performance: By returning a native integer we remove the need to allocate on the heap, which leads to a 2x speedup with small BigInts. More exact benchmarks will follow in case it's deemed necessary. This can also reduces the amount of BigInts in general, as many people probably keep an integer as a BigInt for longer than necessary, which also has a negative impact on performance.

• type safety: using ReducingDiv/Rem can prevent accidental panics. i.e.

fn calculate_divisor() -> u32 { 7 } 
let bigint: BigUint = BigInt::from(std::u32::MAX as u64 + 1);
let divisor = calculate_divisor();


let scalar_result: u32 = (bigint % divisor).to_u32().unwrap();
// using ReducingRem
let scalar_result: u32 = bigint.reducing_rem(divisor);

in case calculate_divisor gets changed to return a bigger integer type instead, i.e

fn calculate_divisor() -> u64 {
    std::u64::MAX
}

the current version panics while using ReducingRem causes a compile time error instead. As calculate_divisor can be arbitrarily far away from the actual operation, bugs like this are often very unexpected.

Warning

std::iX::MIN.reducing_div(BigInt::from(-1)) should panic, as std::IX::MIN / -1 == std::iX::MAX + 1, meaning that it does not fit into a iX. This is unlike std::iX::MIN / BigInt::from(-1), which is safe, as std::iX::MAX + 1 does fit into a BigInt.