Signed carry carrying_add in bigint_helper_methods

[anisse]

I had this question on the currently unreleased #![feature(bigint_helper_methods)] #85532; on signed carry (probably applies to substraction too ?); I have this test failing with the current code:

assert_eq!(i8::MAX.carrying_add(i8::MIN, true), (0, false));

Playground: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=a161cf42872e087303d1435648e6eceb

Is the test correct ? A carry did happen in an intermediate calculation, but should the overall calculation report a carry ?

[cuviper]

I agree that this is a bug. There's a carry when the calculation is done as unsigned, but this is not the same in signed.

Another example:

    assert_eq!(1i8.carrying_add(-1, false), (0, false));

That incorrectly returns (0, true).

[cuviper]

There's some discussion about that in the tracking issue, starting with #85532 (comment)

[anisse]

There's some discussion about that in the tracking issue, starting with #85532 (comment)

Yeah, it looks like I rehashed the same arguments, that's what I get for reading comments and doc too fast. Still, I think that this is surprising enough that it would be nice to address it somehow.

[scottmcm]

I agree this is a bug. It looks like it's implementing the signed version using the unsigned one, returning the same carry flag (https://doc.rust-lang.org/1.56.0/src/core/num/int_macros.rs.html#1366-1369), but that's incorrect.

Here's another demonstration that it needs an update:

assert_eq!(i8::MAX.carrying_add(0, true), (0, true));

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=d376f50304766248792ac98943a2794b

thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `(-128, false)`,
 right: `(0, true)`', src/main.rs:4:1

Would you be up to making a fix PR, @anisse? You can use @rustbot claim to get assigned to this issue.

[anisse]

I have no bandwidth for making a fix right now. Since this was supposed to be helpers for bigint operations, my first idea was to just remove the signed variants. I have no idea if this would be appropriate.

Anyone is welcome to do a proper fix, it shouldn't be too complicated.

[scottmcm]

A thought: What should i8::MIN.carrying_add(-1, false) do?

It feels to me like the carry_out from that should perhaps be -1, since the carry from that is different from the one in i8::MAX.carrying_add(1, false), which would imply that it couldn't be bool anymore.

We do have a type that's -1, 0, or 1: Ordering. I can't decide if that's clever or horrible.

Or should we just delete the signed versions for now?

[Stovent]

I think i8::MIN.carrying_add(-1, false) should return (127, true), because signed and unsigned operations should give the same results, so i8::MIN + (-1) should be computed as 0x80 + 0xFF which gives 0x17F, then truncated to 8-bits which gives 0x7F (127).
Then because -128 - 1 gives -129, which can't be represented as an 8-bits signed number, then there is overflow to me.
Now for the -1, 0, 1 overflow, I don't think it's necessary because the point of the bit is to indicate if it happened or not. The direction of overflow is indicated by the resulting value.

If I am correct, then this raises another question: should intermediate overflow be detected or not ?
for example: i8::MIN.carrying_add(-1, true) gives a result of -128, so the output is the same as the input so no overflow. But if we break down the operations, i8::MIN - 1 overflows to 127, and then (i8::MIN - 1) + 1 overflows back to -128.
In this case should an overflow occur or not ? Considering my previous example, I personally think it intermediate overflow shouldn't be detected because it would be misleading: it would indicate that the sign of the source operands and the result are different while they are the same.

Tho I'd like other's opinion.

[cuviper]

Or should we just delete the signed versions for now?

I think so. The unsigned versions have clear semantics, but it gets weird with signed values, and as a "bigint helper" I'd be surprised to see one that uses signed digits in the first place.