Fix signed integer overflow with midpoint interpolation

[miikkas]

I found this while exploring whether QuickCheck could be updated. Its newer version seems to run more thorough testing, which revealed this problem among others.

---

Assembly comparison

The new algorithm is not really much more complex than the original when comparing the assembly.

I checked the Compiler Explorer results for the following simplified versions, using -C opt-level=1 for compiler option:

#[unsafe(no_mangle)]
pub fn naive_midpoint_i64(lower: i64, higher: i64) -> i64 {
    lower + (higher - lower) / 2
}

#[unsafe(no_mangle)]
pub fn interpolate(lower: i64, higher: i64) -> i64 {
    let (lower_half, lower_rem) = (lower.div_euclid(2), lower.rem_euclid(2));
    let (higher_half, higher_rem) = (higher.div_euclid(2), higher.rem_euclid(2));
    lower_half + higher_half + (lower_rem * higher_rem)
}

The old algorithm produces the following assembly:

naive_midpoint_i64:
        sub     rsi, rdi
        mov     rax, rsi
        shr     rax, 63
        add     rax, rsi
        sar     rax
        add     rax, rdi
        ret

The new algorithm produces the following:

interpolate:
        mov     rcx, rdi
        sar     rcx
        and     edi, esi
        mov     rax, rsi
        sar     rax
        add     rax, rcx
        and     edi, 1
        add     rax, rdi
        ret

So it seems the new algorithm is two instructions longer.

I ran additional testing locally with the following command to ensure the changed algorithm returns the exact same results as the previous one:

QUICKCHECK_TESTS=100000000 cargo test --lib test_midpoint_algo_eq_naive_algo_i64

Something I'm a bit unsure about is whether there are any additional types Midpoint should be implemented for.