The carry in signed carrying_mul on integers should be unsigned

[dzimmanck]

I tried this code:

// use signed carry_mul to chain two multiplies (x*y) + (x*y) >> 64
let carry: i32 = 0;
let x: i32 = 200000;
let y: i32 = 100000;
let (carry, prod) = x.carrying_mul(y, carry);
let (carry, prod) = x.carrying_mul(y, carry);

// do the calculation with larger integers
let large = i64::from(x) * i64::from(y);
let carry = large - ((large>>32)<<32);
let expected = ((large + carry)>>32) as i32;

assert_eq!(expected, prod);

I expected to see this happen: I expected the "prod" to be 5.

Instead, this happened: The product is 4 due to the carry in the first calculation being negative (overflowing) causing it to accumulate incorrectly.

Meta

rustc --version --verbose:

rustc 1.58.0-nightly (db062de72 2021-11-01)
binary: rustc
commit-hash: db062de72b0a064f45b6f86894cbdc7c0ec68844
commit-date: 2021-11-01
host: x86_64-pc-windows-msvc
release: 1.58.0-nightly
LLVM version: 13.0.0

[matthewjasper]

cc #85532

[dzimmanck]

I'm not in a position to get setup to do a well articulated pull request at the moment, but IMO, the change is simple. These should always be UNSIGNED.

[scottmcm]

Hmm, I think it might help for the comment on these methods to clarify exactly what the interpretation of the output values are. For unsigned it's obvious enough (as it's self * rhs + carry = out.0 + out.1 * (MAX + 1)), but the asymmetrical range of signed numbers makes that less clear.