type EGcd

bend-collections-laws-math@1.0.0.0 · src/math/number.bend:15

import Base

15# gcd(a, b) and signed Bezout coefficients split into magnitudes and a sign:
16#   neg == False:  a * x == gcd + b * y      (a*x - b*y == gcd)
17#   neg == True:   b * y == gcd + a * x      (b*y - a*x == gcd)
18# Python's egcd would return one negative coefficient; the unsigned library
19# returns both magnitudes and says which side carries the minus sign.
20type EGcd is Data:
21  EG{gcd: Nat, x: Nat, y: Nat, neg: Bool}