Join GitHub today
GitHub is home to over 50 million developers working together to host and review code, manage projects, and build software together.
Sign upmath/extended_euclidean_algorithm cannot properly handle negative numbers #2630
Comments
|
Hey, thank you for pointing this out. It also seems that the Euclidean algorithm for GCD is not able to handle negative numbers as well: $ python greatest_common_divisor.py
Enter two integers separated by comma (,): -3,9
greatest_common_divisor(-3, 9) = -3
By iterative gcd(-3, 9) = 3
$ python greatest_common_divisor.py
Enter two integers separated by comma (,): 3,-9
greatest_common_divisor(3, -9) = 3
By iterative gcd(3, -9) = -3
$ python greatest_common_divisor.py
Enter two integers separated by comma (,): -3,-9
greatest_common_divisor(-3, -9) = -3
By iterative gcd(-3, -9) = -3
$ python greatest_common_divisor.py
Enter two integers separated by comma (,): 3,9
greatest_common_divisor(3, 9) = 3
By iterative gcd(3, 9) = 3Can you make two separate PRs to correct the algorithms? |
dhruvmanila
added a commit
that referenced
this issue
Oct 7, 2020
* add type hints to math/extended euclid * math/extended euclid - add doctest * math/extended euclid: remove manual doctest * change algorithm for negative numbers * improve naming of variables * Update extended_euclidean_algorithm.py Co-authored-by: Dhruv <dhruvmanila@gmail.com>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Think there is a mistake in the algorithm implemented.
By definition, gcd (a,b) = gcd (a,-b) = gcd (-a,b) = gcd (-a,-b)
So for a = 1, b = 4, the gcd is 1.
eqn1: 0(4) + 1(1) = 1 (correct)
eqn2: 0(4) + 1(-1) = -1 (sign incorrect)
eqn3: -1(1) + 1(-4) = -5 (sign and value incorrect)
eqn4: 1(-1) + 0(-4) = -1 (sign incorrect)