Integer::extended_gcd should not permit unsigned value.

[aobatact]

This code fails to get the y value, with the error 'attempt to subtract with overflow'.

#[test]
fn extended_gcd_test(){
  use num_integer::Integer;
  let _x = 10.extended_gcd(&4);
  let _y = 10_u32.extended_gcd(&4);
}

[aobatact]

May be we can require Self: Signed for extended_gcd

[cuviper]

Yeah, we do require Signed on extended_gcd_lcm, but that was overlooked on extended_gcd. Unfortunately it requires a breaking change to add that constraint.

[aj-r]

Alternatively, it's possible to support extended_gcd for unsigned integers as described here: https://stackoverflow.com/q/67097428/1299394, which would avoid a breaking change.

Edit: because x and y must both be positive for unsigned integers, you'd need to modify the check() function used for testing - instead of assert_eq!(gcd, x * a + y * b); it would need to be something like:

assert_eq!(
  gcd,
  (x * a + y * b) % (a * b),
);

[cuviper]

@aj-r interesting, thanks! I'm open to "fixing" unsigned with that kind of implementation, as long as we're careful to document the difference -- and ideally how to reconstruct what the signed result would have been.

[cuviper]

Maybe we could then drop Signed from extended_gcd_lcm -- but I think that's technically a breaking change for anyone that overrode that method, if they depended on the conditional Signed constraint in their impl. What a mess...

[ktsimpso]

Fwiw I was recently bitten by this. But I was running in release mode so the program didn't crash. But half the time my algorithm was spitting out weird incorrect values because the coefficient I used was the under-flowed value. Switching to a signed type was easy enough for me in this particular case but I lost a few hours.

My expectations as a consumer would have been either the unsigned types did not have this method, or only produced results in the domain of that unsigned type as @aj-r mentioned. (I consider underflow outside of the domain).

As for backwards compatibly, as a consumer and I saw my build break because I used an unsigned type with this method and had silent bugs in my program because of it I think I would be thankful.