Skip to content

Integer::extended_gcd should not permit unsigned value. #40

Open
@aobatact

Description

@aobatact
Contributor

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);
}

Activity

aobatact

aobatact commented on Apr 26, 2021

@aobatact
ContributorAuthor

May be we can require Self: Signed for extended_gcd

changed the title [-]Integer::extended_gcd fails for unsigned value.[/-] [+]Integer::extended_gcd should not permit unsigned value.[/+] on Apr 26, 2021
cuviper

cuviper commented on Apr 26, 2021

@cuviper
Member

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

aj-r commented on Jan 8, 2024

@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

cuviper commented on Jan 8, 2024

@cuviper
Member

@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

cuviper commented on Jan 8, 2024

@cuviper
Member

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

ktsimpso commented on Dec 18, 2024

@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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @cuviper@ktsimpso@aj-r@aobatact

        Issue actions

          Integer::extended_gcd should not permit unsigned value. · Issue #40 · rust-num/num-integer